다이나믹 프로그래밍

[백준 20181] 꿈틀꿈틀 호석 애벌레 - 효율성 C++

20181번: 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net 다이나믹 프로그래밍, 투 포인터 코딩꿈나무 조정현 : 네이버 블로그 빠르게 꾸준히 blog.naver.com 정현님의 추천문제를 풀어보았다! 1. 문제 해결 아이디어 [백준 1644] 소수의 연속합 C++ 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 수학, 두 포인터, 정수론 1. 문제풀이 아이디어 에라토스테네스의 체를 이용해서 N까지의 소수를 배열에 순서 hye..

[백준 1328] 고층 빌딩 C++

1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 다이나믹 프로그래밍 1. 문제 해결 아이디어 일반적인 dp문제는 작은 부분 문제들을 해결하면서 큰 문제의 답을 찾는 느낌인데 이 문제는 조금 다른 느낌이다. (도저히 안 풀려서 힌트를 얻었다) 일단 dp배열은 dp[최대 높이][왼쪽에서 보이는 건물 수][오른쪽에서 보이는 건물 수] 이렇게 설정했다. dp배열을 정해주는 건 어렵지 않았다. 그리고 bottom up 방식으로 푸는 게 좋을 것 같다는 느낌이 크게 들었었다. 그런데 점화식을 도출하기가 정말 어려웠다. ..

[백준 4811] 알약 C++

4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 다이나믹 프로그래밍 1. 문제 해결 아이디어 dp[한 조각 알약의 개수][반 조각 알약의 개수]를 통해서 메모이제이션을 해주면 쉽게 풀린다. 한 조각 알약이 0개라면 앞으로 반 조각을 먹는 경우밖에 없으므로 return 1을 하는 기저 조건이 된다. 재귀 함수 내부에서는 한 조각 알약의 개수가 0보다 크면 한 조각을 빼고 반 조각을 추가해서 재귀 호출을 하고 마찬가지로 반 조각 알약의 개수가 0보다 크면 반 조각만 빼고 재귀호출을 하는 식으로 구현을 했다. 2. 코드 top d..

[백준 2240] 자두나무 C++

2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 다이나믹 프로그래밍 1. 문제해결 아이디어 cnt초가 지났고, s번 움직였고, 사람 자두가 loc에 있을 때의 최댓값을 메모이제이션 해주었다. 사람의 위치가 그대로 라면 cnt가 T가 되기 전까지 진행이 가능하다. 사람의 위치를 바꾼다면 s가 W가 되기 전까지 위치를 바꿀 수 있다. 현재 위치에 따라서 자두를 먹는지, 못 먹는지를 판단해서 결과에 1을 더할지 말지를 결정한다. 2. 코드 top-down 방식으로 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 ..

[백준 1005] ACM Craft C++

1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 위상 정렬, 다이나믹 프로그래밍 1. 문제해결 아이디어 indegree를 활용한 위상 정렬을 하는 문제이다. 위 그림에서 각각의 phase는 다음 phase로 넘어가기위해 모두 해결해야하는 과제와도 같다. 예를 들어서 phase2에서 phase3로 넘어가려면 phase2에 있는 건물을 모두 건설해야 넘어갈 수 있다. 따라서 phase2에서 가장 오래걸리는 건물이 해당 phase에서 걸리는 시간이 되고, 이전 phase의 최대 시간만큼만 next phase의..

[백준 2011] 암호코드 C++

2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 다이나믹 프로그래밍 1. 문제해결 아이디어 현재 자릿수에서 어떤 암호가 만들어 질 수 있는지 dp를 이용해서 해결해야한다. 우선 0은 암호로 바꿀 수 없다. 하지만 0 이전에 1 또는 2가 있다면 암호로 바뀔 수 있다. 숫자 3 이상과 이어지는 암호는 없다. 현재 숫자가 2인 경우 다음 숫자가 0 ~ 6 인 경우만 숫자 2개를 사용해서 암호를 만들 수 있다. dp배열 : dp[i][2] -> i번 자리수 이후로 숫자를 1개 또는 2개를 사용해서 만들 수 있는 경우를 저장하는 배열..

[백준 1309] 동물원 C++

1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 다이나믹 프로그래밍 기초 1. 문제풀이 아이디어 row행에서 사자를 놓는 모든 경우의 수 = row행에 사자를 놓지 않는 경우 + row행의 1번에만 사자를 놓는 경우 + row행의 2번에만 사자를 놓는 경우 row행에 사자를 놓지 않는 경우 = row+1행에 사자를 놓지 않는 경우 + row+1행의 1번에만 사자를 놓는 경우 + row+1행의 2번에만 사자를 놓는 경우 row행의 1번에만 사자를 놓는 경우 = row+1행에 사자를 놓지 않는 경우 + row+1행의 2번에만 사자를 놓는 경우 row행의 2번에만 사자를 놓는 경우 = row+1행에 사자를 놓지 않는 경우 + row+1행의 1번에만..

[백준 2449] 전구 C++

2449번: 전구 입력의 첫 번째 줄에는 전구의 수를 나타내는 양의 정수 N과 전구가 표현할 수 있는 색의 수 K가 주어진다. 단, N은 1이상 200이하의 정수이며, K는 1이상 20이하의 정수이다. 두 번째 줄에는 N개 전 www.acmicpc.net 1. 문제풀이 아이디어 전구를 A, B 두 부분으로 나누고, A의 시작 지점의 색깔과 B의 시작 지점의 색깔을 재귀적으로 같게 한다면 A, B 모두 같은 색이 될 것이다.. - A부분의 색을 같게 하는데 필요한 작업의 수 + B부분의 색을 같게 하는데 필요한 작업의 수 + 현재 A, B의 첫 번째 전구의 색을 같게 하는데 필요한 작업의 수 2. 코드 설명 dp[st][ed] : 전구 배열에서 st부터 ed까지의 전구를 모두 같은 색으로 맞추는데 필요한 ..

[백준 2602] 돌다리 건너기 C++

2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 돌대가리 건너기 다이나믹 프로그래밍 처음에 너무 어렵게 생각했다.. dp배열을 2차원으로 두고 별의별 조건들을 걸면서 했더니 머리만 아프고 문제는 예제입력조차 풀리지 않았다.. 결국 어쩔 수 없이 구글을 참고했는데.. 단순히 3차원 dp배열을 설정해주면 아주 쉽게 풀리는 문제였다 dp[현재 돌다리 상의 위치][다리 종류(천사or악마)][지금까지 밟은 문자열 개수] 처음 dp배열을 -1로 초기화 시켜주고 현재 dp값은 현재 돌다리 상의 위치로 부터 갈 수 있는 모든 돌다리의..

[백준 14501] 퇴사 C++

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net dp와 브루트포스 방식을 모두 적용할 수 있는 좋은 문제이다! solve1은 브루트 포스와 dp를 적용해서 O(n^2)에 풀 수 있는 방법이다 solve2는 solve1과 논리는 같지만 top-down방식으로 재귀함수를 이용한 방법이다 solve3는 동적계획법을 최대한 활용해서 Pi, Ti를 뒤에서부터 탐색하는 방법을 사용해 O(N)만에 해결하는 방법이다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 5..