다이나믹 프로그래밍 (34) 썸네일형 리스트형 [백준 / BOJ] 1937 욕심쟁이 판다 문제 출처 : www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net N*N크기의 대나무 숲에있는 판다는 한 지역의 대나무를 다 먹으면 상하좌우중 한 방향으로 움직일수있다. 단, 이때 움직인곳은 전 지역보다 대나무가 많아야한다. 풀이 9달전에 풀다가 틀렸었는데, 알고리즘 공부를 더 하고서야 맞췄다. (9달전에는 바텀업 구현을 못해서 풀지 못했음) DFS와 DP를 합친 문제다. 1. (i ~ N) (j ~ N) 까지 전부다 돌려준다. 2. (i,j)점에서 시.. [백준 / BOJ] 1932 정수 삼각형 문제 출처 : www.acmicpc.net/problem/1932 1932번: 정수 삼각형 문제 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최� www.acmicpc.net 정수 삼각형을 입력받았을때, 합이 최대가 되는경로를 찾는문제이다 (각 층에선 한 정수만 더 할수있음) 예를들어 을 입력받으면, 최대경로는 1 -> 3 -> 6 = 10이 된다. 풀이 N을 입력을 받고 정수삼각형의 각 정수 입력마다 최댓값을 찾아줬다. 위 정수삼각형에서 규칙을 찾을수있는데, 1층에는 정수가 1개, 2층에는 정수가 2개 ,3층에는 3개...순으로 늘어.. 이전 1 2 3 4 5 다음
