Dev_Diary

https://www.acmicpc.net/problem/1146브루트 포스나 BFS 의 식으로도 풀 수 있지만 시간제한에 걸리게 됩니다.다른 방법을 찾아봅시다. 우리는 N 명의 학생을 줄세워야 합니다.그 중 번호가 가장 큰 N 번째 학생을 P 번째 순서에 줄 세우는 경우를 생각해보겠습니다.그럼 남은 N-1 명의 학생을 줄 세워야 하는데, 어차피 수의 대소만이 중요하기 때문에 지그재그 패턴만 맞으면 어떤 학생이 어디에 서던 중요하지 않습니다.즉 N 번째 학생을 P 번째 세우고 양 옆에 남은 학생들을 다시 줄세우는 작은 단계로 쪼갤 수 있습니다.즉 이 문제를 DP 로 풀 수 있습니다. N 명의 학생 중 P 번째 자리에 N 번째 학생을 줄세운다고 생각하겠습니다.해당 경우를 A_NP 라고 부르겠습니다. P 가..

https://www.acmicpc.net/problem/1153합으로 구해야 하는 네 개의 소수 조합을 모두 찾는다면 시간초과가 발생합니다.그렇다면 조합의 수를 줄여야 하는데, 여기서 사용할 수 있는 이론이 골드바흐의 추측입니다.아직 증명되지는 않았지만 충분히 큰 수에 대해 모두 성립하는 추측이므로 해당 문제에서 사용할 수 있습니다. 모든 짝수에 대해 두 개의 소수의 합으로 표현할 수 있다는 것이 주된 내용인데, 그렇다면 N 이 주어졌을 때 미리 두개를 정해놓고 두개만 조합으로 구할 수 있습니다. N 이 짝수인 경우, 골드바흐 추측을 사용하기 위해 N - K 도 짝수로 만들어야 합니다.그렇다면 K 도 짝수이므로 합이 가장 작은 짝수의 조합인 [2, 2] 를 미리 정해놓을 수 있습니다.N 이 홀수인 경우..