도미노 잇기 > 문제은행

본문 바로가기


문제은행

1059 : 도미노 잇기

제한시간: 1000 ms    메모리제한: 256 MB
해결횟수: 4 회    시도횟수: 165 회   



도미노란 2개의 정사각형을 붙여 2x1의 사각형의 형태를 띠는 블록을 뜻한다. 각 정 사각형에는 0개부터 6개의 점이 찍혀 있다. 알다시피 도미노로 하는 게임은 무궁무진하다고 말 할 수 있을 정도로 많이 있다. 그 중에 가장 많이 행해지는 게임은 도미노를 이어 붙이는 게임인데 아래의 그림과 같이 점의 개수가 같은 정사각형을 가진 도미노를 잇는 게임이다.

 

11800286b18638b9b862cfe91853162f_1462258 

위에서 보다 시피 한 정사각형에는 반드시 자신과 동일한 점의 개수를 가지는 다른 도미노의 정사각형을 한 개만 이어 붙여야 한다. 나타날 수 있는 도미노 블록의 종류는 다음과 같다: 0-0, 0-1, 0-2, 0-3, 0-4, 0-5, 0-6, 1-1, 1-2, 1-3, 1-4, 1-5, 1-6, 2-2, 2-3, 2-4, 2-5, 2-6, 3-3, 3-4, 3-5, 3-6, 4-4, 4-5, 4-6, 5-5, 5-6, 6-6. 도미노는 양쪽으로 자유자재로 사용 할 수 있다. 예를 들어 1-6의 경우 1/6 혹은 6/1로 사용이 가능하다는 것이다. 사용 가능한 도미노가 주어졌을 때 얼마나 많은 도미노를 이을 수 있는지를 알아보는 프로그램을 작성하라. 같은 종류의 도미노는 여러 번 나올 수 있다.


첫 번째 줄에는 도미노의 개수 N(1≤N≤1,000)이 입력된다. 그 다음 줄부터는 사용 가능한 N 개의 도미노의 종류에 대한 입력이 들어오는데 한 줄은 도미노 블록 하나를 뜻하며 2개의 숫자는 도미노의 정사각형에 찍혀있는 점의 개수를 뜻한다.



입력에 대해 가장 길게 이을 수 있는 도미노의 개수를 출력한다.


[Copy]
6
2 5
0 1
1 6
2 3
1 2
4 5
[Copy]
4






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.