BOJ 썸네일형 리스트형 백준 11066 / 파일 합치기 연속 연속 연속 연속 다이내믹프로그래밍 문제 D[i][j]를 i부터 j까지 파일을 하나로 합치는데 드는 최소 비용이라고 하자. 메인 로직은 i부터 j 사이에 있는 어느 k에 대해 D[i][j] = min( D[i][j], D[i][k] + D[k+1][j] + i부터 j까지 다합친 크기) 이다. 여기서 최소값이기 떄문에 D를 연산에 들어가기 전 최대값으로 초기화해주어야한다. i부터 j까지 다 합친 크기를 한번 더 더해주는 이유는 i-k부터 끊고 k+1-j까지 끊은 걸 합쳐줄 떄 비용이 발생하기 떄문. for문으로 풀기엔 case 정의가 어려워 재귀로 풀어야한다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243.. 백준 11058 / 크리보드 d[n]을 n번 눌러서 출력할 수 있는 A의 최대 개수라고 하자. 마지막 입력 그러니까 n-1에서 n으로 넘어가는 입력에 따라 경우를 나누어보자. 1. 마지막에 1를 눌렀을 경우 d[n-1]에서 A가 하나 추가되니 d[n]은 d[n-1]+1이다. 2. 마지막에 2를 눌렀을 경우 마지막에 2를 누르는 경우는 최대값이 될 수가 없음으로 무시 3. 마지막에 3을 눌렀을 경우 마지막에 3을 누르는 경우 또한 최대값이 절대 될 수가 없음으로 무시 4. 마지막에 4를 눌렀을 경우 n이 7이상인 모든 경우엔 마지막에 4를 누르고 끝나야 최대값이다. 4를 눌렀다는 것은 2와 3을 이전에 수행했다는 뜻. 고로 n-3때 2를 누르고 n-2때 3, n-1에 4를 누르는 경우이다. 그러므로 d[n] = 2*d[n-3] 그러나.. 백준 2293 / 동전 1 다이나믹 프로그래밍 문제 풀이법은 1,2,3 더하기 4 문제와 같다. (https://naivep.tistory.com/66) 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우라는 뜻은 중복을 허용하지 않는다는 뜻. d[i]가 i원을 만들 수 있는 경우의수라고 하면 모든 동전마다 그 동전으로 i원을 만들 수 있는 경우의 수를 d[i]에 추가해준다. 그렇기 때문에 for문의 순서는 for(동전의 개수)for(0부터 k까지) 가 되고, 중복이 허용되는 경우는 for(0부터 k까지)for(동전의 개수) 로 하면 된다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940#include#include#include#incl.. 백준 15989 / 1,2,3 더하기 4 1,2,3을 이용하여 수를 만드는데 중복 없이 만드는 경우의 수를 묻는 문제이다. 코드를 보면 코드 1234567891011121314151617181920212223242526272829303132333435363738#include#include#include#include#include#include#include using namespace std; int d[10001]; int main() { //freopen("Text.txt", "r", stdin); int testcase; cin >> testcase; int nums[3] = { 1,2,3 }; d[0] = 1; for (int j = 0; j > n; cout 백준 10942 / 팰린드롬? 거꾸로 읽어도 같은 것을 팰린드롬이라고 한다. 처음엔 스트링으로 받은다음 reverse를 사용하여 풀어보려 했는데 시간초과. O(MN)인데 M의 최대가 백만이니 시간초과가 날수 밖에. 그리하여 다이나믹 프로그래밍으로 풀었다. D[S][E]를 S번째 수부터 E번째 수까지 팰린드롬이면 1 아니면 0 아직 구하지 못했으면 -1로 설정했다. 탑다운 방식으로 구현했는데 로직은 1. S==E 이면 팰린드롬 2. S+1 == E 일때 arr[S]==arr[E]이면 팰린드롬 다르면 X 3. arr[S]==arr[E]일때 D[S+1][E-1]가 1이면 팰린드롬 아니면 X 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445.. 백준 1890 / 점프 우선, 경로의 개수의 최대값이 2^63-1이니 BFS로 풀면 메모리초과가 난다. (ex) 모든 칸이 1로된 100x100 게임판) 다이나믹 프로그래밍으로 풀어야 한다. d[i][j]가 i,j에 도착할 수 있는 모든 경우의 수라고 했을때, 0보다 크고 i보다 작은 어떠한 k에 대해서 map[k][j] + k가 i가 되는 경우를 찾는다면, d[i][j]는 d[k][j]로 이루어질 것이다. 또한, map[i][k] + k가 j가 되는 경우를 찾는다면 d[i][j]는 d[i][k]로 이루어질 것이다. d의 값에 2^63-1이 들어갈 수 있으니 d는 long이상을 선언해주어야한다. 코드 (34~43번째 코드가 핵심) 123456789101112131415161718192021222324252627282930313.. 백준 11048 / 이동하기 다이나믹 프로그래밍 문제 가중치는 같지만 사탕을 가져올 수 있는 최대값을 문제이기 때문에 BFS로 풀 수 없다. 다양한 점화식이 있지만 가장 간단한 방법을 사용했다. D[i][j]가 i,j에 도착했을때 가진 사탕의 최대값, map[i][j]가 i,j에 놓인 사탕의 개수라 가정했을 때, 위에서 왔을 경우 : D[i][j] = D[i-1][j] + map[i][j] 왼쪽에서 왔을 경우 : D[i][j] = D[i][j-1] + map[i][j] 왼쪽 위 대각선에서 왔을 경우 : D[i][j] = D[i-1][j-1] + map[i][j] 이기 떄문에 D[i][j]는 max(D[i-1][j], D[i][j-1], D[i-1][j-1]) + map[i][j]이 된다. 문제의 조건인 (1,1)에서 시작하여 (n,.. 백준 15558 / 점프 게임 최단거리가 있으면 갈 수 있다라는 뜻이기 떄문에 BFS로 풀 수 있다. n보다 큰 모든 칸을 갈 수 있는 칸으로 설정했고, k의 최대치가 100000으로 맵의 크기를 200000으로 설정했다. tuple을 사용하여 시간초를 추가해주었다. 시간초는 뒤로 이동하는 경우에만 영향을 준다. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include#include#include#include#include#include using namespace std; int map[2][200000];bool check[2.. 이전 1 2 3 4 5 6 ··· 10 다음
