ntopia   6년 전

2008년 당시에 올라왔던 풀이 문서를 그대로 공유합니다. 제가 작성한 것은 아니고 kcm1700님이 작성하셨던 문서입니다.

드래그하면 보이도록 해놨습니다


1. 파스칼 삼각형

아무렇게나 해도 됩니다.


2. 즐거운 게임

수열을 2로 나눈 나머지를 취해주면, 전형적인 다이나믹 문제입니다. 여러 방법이 있지만 한 가지 방법은 D[i][j][0]을 자신이 현재 지운 수들의 합을 2로 나눈 나머지가 0이고, 남은 수열이 i번째에서 j번째라면, 이길 방법이 존재하는가? 로 세우면 됩니다. O(N^2)


3. 사업 방해

DFS로 푸는 것이 생각하기는 쉽지만, 무방향 간선을 방향성 있는 두 간선으로 분리한 뒤 각 간선을 기준으로 화살표가 시작되는 쪽을 서브트리로 놓았을 때를 생각해서 동적계획법을 적용해주면 매우 편한 코딩이 가능합니다. BFS로 queue를 이용할 수 있어서 편하게 쉽게 코딩할 수 있습니다.  O(N)


4. 뒤집기

수열을 원형으로 놓고 적당한 곳에서 시작하여 반대방향으로 훑어주면 답이 됩니다. KMP 문자열 비교에서 쓰인 아이디어로 prefix 다이나믹 테이블을 만들어 빠른 시간내에 비교를 마칠 수 있습니다. (최초로 달라지는 부분이 우리가 관심을 가지는 부분이기 때문) O(N)


5. 수 고르기

heap을 이용해서 a,b,c가 있을 때 b를 택하면 a,b,c를 제거하고 그 자리에 a+c-b 를 넣어줍니다. 최종 결과값은 이 작업을 k번 반복할 때 선택한 값들의 합입니다. 엄밀한 증명은 생략합니다. O(N + K log N)


gunwookim   6년 전

안되는데요?

sgchoi5   6년 전

감사합니다~

댓글을 작성하려면 로그인해야 합니다.