내일(금) 오전 10시까지 ACM하시는 분들 모여주시고

SoC는 김신호씨랑 최홍준씨 오후에 오는대로 시작하겠습니다.

by 잭크 2007.07.05 16:15

invalid-file

2004년 온라인예선 D - 미팅주선

invalid-file

소스코드

invalid-file

입력파일

invalid-file

결과 출력파일


순전히 노가다문제였습니다.
문제를 푸는 Solution은 이미 초반에 파악했지만 막상 구현하는데 꽤나 오랜시간이
걸렸던 문제입니다.
괜히 타율이 낮은게 아니더군요;;
다행히 STL의 힘으로 완성했습니다.
소스코드 보고 익힐 사항은 Vector 자료형의 사용법과 Permutation의 모든 경우의수를
구해주는 next_permutation 메소드입니다.
일단 소스코드를 보고 이해가 안가는 부분은 개인적으로 물어보시기 바랍니다.
시간 나면 Solution과 코드 설명 올리겠습니다;;

by RyuiSaka 2007.07.05 00:58

Problem 99 : Broken Necklace
http://fitzsimmons.ca/beads.html


파란색과 빨간색의 구슬로 이루어진 목걸이가 있다.
목걸이를 특정 지점에서 끊어서, 끊어진 목걸이의 양쪽 끝에서
다른 색의 구슬을 발견할 때 까지 구슬의 개수를 세어나간다.
그렇게해서 얻을 수 있는 최대의 구슬 개수를 찾는 것이 목표이다.
흰색 구슬이 나올 수도 있는데 이 구슬은 원하는 색으로 칠할 수 있다.

풀이 방식 :
목걸이의 구슬별로 잘라서 Circular Doubly Linked List로 만들고,
For 문을 돌려 각 구슬 별로 돌아가면서 해당 구슬을 기준으로 삼아서 목걸이를 끊고,
모든 경우를 고려하였다.

by Raven the Revenger 2007.07.04 20:10
| 1 2 3 4 5 6 7 |