백준 1932번 DP 문제 문제 사이트 해설 제일 위에서 부터 제일 아래까지 내려가면서 자기 자식을 더해서 가장 큰 값을 구하는 문제이다. i가 1->3으로 갈 떄까지 최고 합을 구하면 되는 것입니다. 경우의 수를 보게 되면 ABD / ABE / ACE / ACF 이렇게 4가지가 있다. ABF가 안되는 이유는 당연히 문제에 대각선 왼/오른쪽(자식) 중 선택하라고 했으므로 F는 C의 자식이지 B의 자식이 아니기 떄문에 안된다. 간략하게 배열에 맞게 숫자를 넣어봤다. 그럼 이제 하나씩 더해 보도록 하겠다. 빨강 테두리 부분과 파랑 테두리 부분을 먼저 보면 이 부분의 합을 구하는 방법은 딱 하나 밖에 없다. 예를 들어 (3,1) 까지 더한 값을 구하기 위해서 (3,1) + (1,1) +.(2,1) 이렇게 밖에..

백준 2579 동적 계획법 문제 문제는 위에 링크와 같다. 설명 문제를 간단하게 설명하면 각 계단이 있는데 그 계단에 값이 있고 연속해서 계단을 3번을 건널 수 없고 최대값을 구하는 문제이다. DP[N]을 N개의 계단을 오르기 규칙에 의해 얻은 최대 점수라고 가정하자. N번째 계단은 무조건 밟아야 하기 때문에 N번째 계단이 1번 연속인 경우! N번째 계단이 2번연속인 경우! 이 2가지 경우를 나누어서 생각해 보자. 이제 중요한 3번째 계단이다. (첫번째 경우) N번째 계단이 1번 연속인 경우 N-1번째 계단은 필요 없고, N-2번째 계단의 총점을 합쳐야 합니다. DP[N] = DP[N-2] + A[N] (두 번째 경우) N번째 계단이 2번 연속인 경우 N-1번째 계단은 밟아야 하고, N-2번째 계단은 무..

백준 9663 N-Queen 문제 백트랙킹으로 유명한 n-queen문제이다. 간략하게 문제는 이렇다. N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 위 그림은 체스를 놓을 수 있는 방법중 하나이다. 체스의 퀸은 양 옆, 아래 ,대각선을 공격할 수 있기 때문에 조건으로 양 옆,아래,대각선 이렇게 있으면 안된다. 처음에 과연 어떻게 체스의 위치를 알 수 있을까 생각을 하다가 좌표를 그려보았다. 그리고 각 행에 한 개의 체스만 놓을 수 있다는 것을 알게 되었다. 그러면 각 행에 체스 퀸을 놓고 DFS형식으로 문제를 풀면 되겠다고 생각을 하였고 체스 퀸을 하나 놓을 때 마다 위치의 조..