https://www.acmicpc.net/problem/17498 17498번: 폴짝 게임 첫 번째 줄에 행의 개수 N과 열의 개수 M (2 ≤ N×M ≤ 200,000, 2 ≤ N) 그리고 최대 점프 거리 정수 D (1 ≤ D ≤ 10) 가 주어집니다. i+1 번째 줄에는 i (1 ≤ i ≤ N) 번째 행에 있는 쓰여있는 정수 ai,1, ai,2, www.acmicpc.net DP 문제다. 정적 할당을 하면 배열의 공간 낭비가 심할 것 같아 동적 할당을 했다. (동적 해제는 까먹음) 입력으로 음수가 들어와 점수의 최대 값이 음수가 될 수 있으므로 dp의 초기값을 int 범위의 최솟값으로 지정했다. 지나온 길에서 거리가 d 이하면 점프가 가능하다. 고로 모든 경우의 수의 점프를 고려해야한다. 행을 움직..
Algorithm/DP
https://www.acmicpc.net/problem/2666 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net DP와 완전 탐색 문제다. DP의 배열을 3차원으로 생성했다. dp[원하는 문을 연 횟수][열린 문 중 왼쪽][열린 문 중 오른쪽] 특정 시점에서 최선의 선택이 다음 선택에서는 최선이 아닐 수도 있기 때문에 완전 탐색을 이용했다. 최대 문의 수가 20이라는 점에서 완전 탐색을 이용해도 시간 초과가 나지 않을 것이라 판단했다. #include #include using namespace std;..
https://www.acmicpc.net/problem/2560 2560번: 짚신벌레 첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0＜a＜b＜d ≤ 10,000이고, 1 ≤ N ≤ 1,000,000이다. www.acmicpc.net DP와 누적 합 문제다. #include using namespace std; long long dp[1000001]; int main() { // 입출력 속도를 단축시키기 위함 ios::sync_with_stdio(0); cin.tie(0); int a, b, d, N;cin >> a >> b >> d >> N; for (int i = 0; i < a; i++) dp[i] = 1; for (int i = a; i = ..
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DP 문제다. 처음 생각한 방법은 2차원 배열을 이용해 1을 포함해 1개로 n을 만드는 경우의 수 2를 포함해 1개로 n을 만드는 경우의 수 ... 1을 포함해 2개로 n을 만드는 경우의 수 2를 포함해 2개로 n을 만드는 경우의 수 ... ... ... ... 이렇게 배열 자체를 n을 구하기 위한 경우의 수를 구하려 했다. 겹치는 부분을 생각할 수도 없고 규칙도 찾기 어려워 버렸다. 두 번째 생각한 방법은 모든 경우의 수를 다 적고 거기에서 규칙적인 변화를 찾았다. 작은 규칙을 찾긴 했지만 사용할 수 있는 방법이 없고, ..
https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net DP 문제다. 이전 값들의 접근으로 배열을 이용했다. 입력 받은 가치들을 배열에 저장하고 그 값들을 탐색했다. 동전의 가치를 더해서 원하는 수를 만들 수 있기 때문에 dp[원하는 값 - 가치] + 1을 하면 그 값을 만들기 위한 동전의 수를 알 수 있다. 모든 가치의 값들을 탐색하면서 그 중 최솟값을 찾는다. 주의할 점은 1. 배열의 범위를 벗어나선 안된다. 즉, 원..
