11개의 댓글이 있습니다.
-
-
soyoja -
말 나온김에 저도 질문하나 할께요 ^^
ICPC 서울대회 2003 년도 문제, finding liar ( http://acm.pku.edu.cn/JudgeOnline/problem?id=1332 ) 어떻게 푸는 지
알려주세요. DP 일거 같은데 점화식이 안세워지네요 ㅋ
16년 전 link
-
-
-
JongMan -
저도 6년전에 못 풀었던 문젠데 지금 풀었네요 -_-; (수업 안 듣고... orz)
큰 방향만 설명해 봅니다. 모든 사람에게 '거짓말장이', '참말장이' 라는 레이블을 붙였을 때, 이 레이블들이 테스트 결과를 모두 만족한다면 이를 하나의 '시나리오' 라고 합시다.
C[a][b][c][d] = 0번 사람부터 a번 사람까지 중에 b명이 거짓말 장이이고, 0번 사람의 거짓말장이 여부가 c 이고 a번 사람의 거짓말장이 여부가 d 인 시나리오가 존재하는가?
를 동적 계획법으로 계산할 수 있고요. 이렇게 하고 나면 C[n-1][][][] 를 다 뒤져서 참인 것부터 백트랙해 가서, 'X번 사람이 참말장이인 시나리오가 있는가' 를 계산할 수 있습니당..
뭐 소스코드도 길고 메모리도 많이 먹어서 이게 최적의 방법이 아닌건 확실한데 일단 -_-; 써봅니다. 정신이 없어서 설명도 구리지만 양해를 ^^
16년 전 link
-
-
-
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)
16년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
포아
백트래킹으로 하면 안될것같고....
해법좀 가르쳐주세요..
16년 전