![[레벨:0]](./modules/point/icons/default/0.gif "포인트:70point (77%), 레벨:0/30"){kind=icon}
포아백트래킹으로 하면 안될것같고....
해법좀 가르쳐주세요..
해법좀 가르쳐주세요..
2008.09.18 13:48:41 (*.146.211.212)
![[레벨:7]](./modules/point/icons/default/7.gif "포인트:4910point (85%), 레벨:7/30"){kind=icon}
JM저도 6년전에 못 풀었던 문젠데 지금 풀었네요 -_-; (수업 안 듣고... orz)
큰 방향만 설명해 봅니다. 모든 사람에게 '거짓말장이', '참말장이' 라는 레이블을 붙였을 때, 이 레이블들이 테스트 결과를 모두 만족한다면 이를 하나의 '시나리오' 라고 합시다.
C[a][b][c][d] = 0번 사람부터 a번 사람까지 중에 b명이 거짓말 장이이고, 0번 사람의 거짓말장이 여부가 c 이고 a번 사람의 거짓말장이 여부가 d 인 시나리오가 존재하는가?
를 동적 계획법으로 계산할 수 있고요. 이렇게 하고 나면 C[n-1][][][] 를 다 뒤져서 참인 것부터 백트랙해 가서, 'X번 사람이 참말장이인 시나리오가 있는가' 를 계산할 수 있습니당..
뭐 소스코드도 길고 메모리도 많이 먹어서 이게 최적의 방법이 아닌건 확실한데 일단 -_-; 써봅니다. 정신이 없어서 설명도 구리지만 양해를 *^^*
2008.09.18 09:33:26 (*.146.67.10)
![[레벨:4]](./modules/point/icons/default/4.gif "포인트:2150point (95%), 레벨:4/30"){kind=icon}
Toivoa2004 온라인예선 F라면 항상 3*3이니 뒤집는 방법이 8가지 (3열 + 3행 + 2대각선) 뿐입니다.
같은 방향으로 두 번 이상 뒤집는 경우는 의미가 없으니 경우의 수가 2^8 = 256이 되기 때문에 특별한 방법 없이 모든 경우를 시도해봐도 됩니다.
같은 방향으로 두 번 이상 뒤집는 경우는 의미가 없으니 경우의 수가 2^8 = 256이 되기 때문에 특별한 방법 없이 모든 경우를 시도해봐도 됩니다.
![[레벨:1]](./modules/point/icons/default/1.gif "포인트:190point (52%), 레벨:1/30"){kind=icon}
kcm1700
2008.09.19 02:04:32 (*.140.89.168)
![[레벨:3]](./modules/point/icons/default/3.gif "포인트:985point (68%), 레벨:3/30"){kind=icon}
고글F - sorting..
특별한 건 없고, 입력이 들어왔을때 두개씩 옮길 수 있으므로
가장 작은 수를 찾아서 그 뒤 수와 함께 옮기면서 정렬을 합니다.
그러다가 마지막에 맨뒤의 두수가 남았을때, 이수가 정렬되 있으면 Yes, 뒤집혀졌으면 No..
문제는 1 2 5 4 3 이런 식으로 3을 정렬해야 하는데 맨 뒤에 있는 경우인데.. 그냥 4 3 을 앞으로 옮긴 후 하던대로 해 줬음..
====sccc 게시판에서..====
특별한 건 없고, 입력이 들어왔을때 두개씩 옮길 수 있으므로
가장 작은 수를 찾아서 그 뒤 수와 함께 옮기면서 정렬을 합니다.
그러다가 마지막에 맨뒤의 두수가 남았을때, 이수가 정렬되 있으면 Yes, 뒤집혀졌으면 No..
문제는 1 2 5 4 3 이런 식으로 3을 정렬해야 하는데 맨 뒤에 있는 경우인데.. 그냥 4 3 을 앞으로 옮긴 후 하던대로 해 줬음..
====sccc 게시판에서..====
2008.10.01 16:10:56 (*.44.133.5)
astein좀 더 수학적으로 접근해 보도록 할게요. S = a1, a2, a3, ..., an 이라는 수열이라고 할 때, f(S)를 다음과 같이 정의합니다.
f(S) = i < j 이고 ai > aj를 만족하는 모든 경우의 수.
즉 S = {1, 3, 4, 2} 의 경우라면 f(S) = 2가 되겠지요. 3이 2보다 앞에 있고, 4도 2보다 앞에 있으니까요..
문제에서 주어진 연산을 한다고 가정합시다. 원래 수열 S에서 임의의 연산을 한 후의 수열이 S'라고 보면
f(S') = f(S) - 2, f(S), f(S) + 2의 세 가지 경우가 나옵니다. 그런데 우리가 원하는 상태 F( {1, 2, 3, 4...,n} ) = 0이 되기 때문에,
f(S)가 홀수라면 NO, f(S)가 짝수라면 YES라고 할 수 있겠지요.
(물론 주어진 연산으로 임의의 위치에 있는 수를 우리가 원하는 데로 옮길 수 있는지도 증명해야하지만 이건 패스할께요 :D)
말 나온김에 저도 질문하나 할께요 ^^
ICPC 서울대회 2003 년도 문제, finding liar ( http://acm.pku.edu.cn/JudgeOnline/problem?id=1332 ) 어떻게 푸는 지
알려주세요. DP 일거 같은데 점화식이 안세워지네요 ㅋ