dp
-
BOJ) 파일 합치기 (11066 번)알고리즘/백준 2021. 2. 2. 18:22
파일 합치기 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net DP로 분류된 문제인데, 정답률에 비해 굉장히 어렵게 느껴졌다. 연속된 소설 파일들을 합치는데, 연속이 되도록 파일을 합쳐야한다. 즉, 인접한 두 파일만을 합칠 수 있을 때, 가장 최소 비용을 구하는 문제다. 이 문제는 풀지 못했다. 정말 모르겠어서 다른 분들의 풀이를 참고해서 블로그를 포스팅한다. 참고한 링크는 하단에 걸어두었다. dp[i][j]는 i부터 j까지 합쳐지는데 최솟값을 저장한다. ( i ~ j 장 까지 합치는데 드는 최소 비용)..
-
BOJ) 평범한 배낭알고리즘/백준 2020. 8. 28. 16:49
평범한 배낭 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 짐의 개수 n, 버틸 수 있는 무게 k, n개 만큼의 짐의 정보 (무게 w, 가치 v)가 주어진다. 최대한 k에 맞추어, 최대 가치(max v)를 찾는 문제다. dp의 크기를 최대 가치 k까지 입력받을 수 있도록, k+1만큼 생성해준다. 짐의 정보를 순회하면서 w와 v를 가져온다. 그리고 k 부터 w까지 무게를 줄여나가면서, 현재 무게 ( i )의 dp값(가치) 과 dp[i-w] ..
-
BOJ) 점프알고리즘/백준 2020. 8. 27. 15:30
점프 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거�� www.acmicpc.net 풀이 0,0을 시작으로 n-1,n-1까지 도달할 수 있는 경우의 수를 구하는 문제다. 각 인덱스에 적혀있는 칸만큼 오른쪽 혹은 아래로 움직일 수 있으며, 범위 밖으로는 움직일 수 없고 칸에 적힌만큼 정확히 이동해야한다. 그래서 모든 인덱스를 순차적으로 돌면서 dp 값이 0이 아니고, 해당 인덱스가 움직일 수 있는 값이 0이 아닐 때, dp를 최신화해줬다. 경우의 수를 누적시키며 답을 찾아간다고 생각하면 된다. 처음에는 dfs로 풀려고 생각하다가, 경로의 개..
-
BOJ) 가장 큰 정사각형알고리즘/백준 2020. 8. 26. 15:22
가장 큰 정사각형 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 전에 푼 적이 있는 문제여서, 비교적 쉽게 풀 수 있었다. 당시에는 어떻게 풀어야하는지 막막했었는데, 그때 봤던 풀이가 아직 머릿속에 남아있었다. 우선, 맵을 돌면서 1인 경우에 좌측 상단, 좌측, 상단 세 군데를 확인한다. 세 곳의 최소값 +1(자기자신)이 dp의 값이 된다. dp[y][[x] += min(dp[y-1[[x-1], dp[y-1][x], dp[y][x-1]) 이 된다는 소리다. 변이 2인 사각형은 2로, 3을 만족하는 사각형은 3으로 값이 정해지는 것이다. (손으로 위의 식을 풀어가다보면 쉽게..
-
BOJ) 욕심쟁이 판다(1937, JAVA)알고리즘/백준 2020. 8. 25. 17:54
욕심쟁이 판다 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 풀이 메모이제이션을 활용한 dp문제다. 생각보다 너무 어려웠다. 알고리즘을 조금 쉬었다가 메모이제이션을 적용시켜서 dp를 활용하려니까 감이 잡히지 않았다. 그래서 다른 사람들의 풀이를 보면서 이해했다. 먼저, out of index를 방지해줄 inInArea 메소드와 움직일 수 있는 조건인지 확인하는 canMove 메소드를 만들었다. 이후, dfs 메소드인 findBamboo를 통해 문제의 조건에 따라 움직이며 최대 날을 구했다. 해당 위..
-
BOJ) 동물원 (1309, JAVA)알고리즘/백준 2020. 8. 24. 16:44
풀이 코드 라인을 보면 아주 간단한 문제라고 여겨지겠지만, 점화식을 도출하는 것이 어려웠다. 더 사실대로 말하자면, 혼자 도출하지 못했고 다른 풀이에서 점화식을 얻어왔다고 표현하는게 더 맞는 것 같다. 처음에는 Combination과 같은 경우를 찾는 식을 활용하는 방향으로 접근했다.하지만 어떤 식도 부합하는 것이 없었고, n=1 ~ n=4까지 직접 경우의 수를 찾아봤다. n=1 => 3n=2 => 7n=3 => 17n=4 => 41 위와 같이 경우의 수가 나왔다.위에서 유추할 수 있는 것은, dp[n] = dp[n-1]*2 + dp[n-2] 라는 식이다.n-1의 경우의 수 *2 + n-2의 경우의 수가 되는데, 왜 이 식이 성립하는지는 아직 명확하지 않다.n이 1씩 증가할 때마다, 2칸이 생기기 때문에..
-
BOJ) 이항 계수 2알고리즘/백준 2020. 8. 8. 15:49
이항 계수 2 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이 nCr 을 구하는 문제다. nCr = n-1Cr-1 + n-1Cr 이라는 공식을 저번에 이어서, 다시 한번 머리에 남기기 위해 포스팅 한다. r이 0일 때와, n일 때 1로 설정하고, 나머지 r에 대해서 위의 공식을 적용하면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public sta..
-
BOJ) 이동하기알고리즘/백준 2020. 8. 2. 00:01
이동하기 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net 풀이 미로에 같힌 준규가 각 방에 놓여있는 사탕을 주워먹으면서 갈 때, 먹을 수 있는 사탕의 최대 갯수를 구하는 문제다. 이 문제는 언젠가 풀었던 것 같다. 아마 프로그래머스 문제 중 하나이지 않을까 싶다. 아무튼, dp를 이용해서 문제를 풀었다. 맵의 처음부터 x축을 순회하면서 좌측과 상단 중 사탕이 더 많은 갯수를 더해가면서 마지막 위치에 도달하게 설정했다. 이후, n, m의 dp값을 출력해서 답을 쉽게 구할 수 있었다. 코드 im..