[백준] 17953번: 디저트

https://www.acmicpc.net/problem/17953 17953번: 디저트 창호는 매일 점심마다 디저트를 먹는다. 그런데 같은 디저트라도 매일 느끼는 맛이 달라진다. 어떤 날에는 마카롱을 먹고 매우 행복함을 느끼는 반면 어떤 날에는 ‘차라리 케이크를 먹는게 나 www.acmicpc.net 이전의 선택을 고려해야 하는 dp 문제다. 날짜 N에 얻을 수 있는 총 만족감의 최댓값을 출력해야 하는데, (n - 1) 일에 먹은 디저트를 n 일에도 먹는다면, n 일의 만족감이 절반(내림)이 된다는 조건이다. 따라서 이전 선택을 고려해야 하므로, 아래와 같이 dp 배열을 정의한다. #define MAXM 11 #define MAXN 10001 // dp[m][n] = n일에 m 디저트를 먹었을 때의 총..

[백준] 13703번: 물벼룩의 생존확률

https://www.acmicpc.net/problem/13703 13703번: 물벼룩의 생존확률 수면에서 k 센티미터 아래에 있는 물벼룩은 1초마다 각각 1/2의 확률로 위 또는 아래로 1 센티미터 이동한다. 물벼룩은 수면에 닿자마자 기다리고 있던 물매암이들에 의해 먹혀 없어진다. 예를 www.acmicpc.net 분기에 따른 경우의 수를 계산하는 dp 문제다. 사실 문제에서 괜히 확률 이야기가 나와서 그렇지, 그냥 경우의 수 문제다. 시간 N의 최댓값이 63, 물벼룩의 위치 K의 최댓값이 63이다. 최악의 경우를 생각해보면, N초 후의 물벼룩의 위치는 최대 126까지 가능하다. 따라서 dp 배열을 아래와 같이 정의한다. #define MAXN 64 #define MAXK 129 typedef lon..

[백준] 11909번: 배열 탈출

https://www.acmicpc.net/problem/11909 11909번: 배열 탈출 상수는 2차원 배열 A[1..n][1..n] (n≥2, n은 자연수)을 가지고 있습니다. 이 배열의 각 원소는 1 이상 222 이하의 정수입니다. 배열을 가지고 놀던 상수를 본 승현이는, 질투심이 불타올라 상수를 A[1][1] www.acmicpc.net 최솟값을 유지하는 dp 문제다. 전형적인 최솟값 구하기 dp 문제이므로 아래와 같이 dp 배열을 정의한다. #define MAXN 2223 // dp[y][x] = (y, x)까지 왔을 때 총비용의 최솟값 int dp[MAXN][MAXN]; int map[MAXN][MAXN]; 문제는 간단하다. 오른쪽과 아래쪽으로만 이동할 수 있고 현재 칸의 수가 다음 칸의 수..

[백준] 16400번: 소수 화폐

https://www.acmicpc.net/problem/16400 16400번: 소수 화폐 구매하려고하는 물건의 값 N(2 ≤ N ≤ 40,000, N은 정수)이 주어진다. www.acmicpc.net 전형적인 배낭 문제인데, 소수를 가지고 푸는 dp 문제다. 여느 배낭 문제와 마찬가지로 아래와 같이 dp 배열을 정의한다. #define MAXN 40001 #define DIVIDER 123456789 // dp[n] = n원을 만들 수 있는 모든 경우의 수 int dp[MAXN]; N의 최댓값이 40000 이므로, 40000 이하의 모든 소수를 먼저 찾아야 한다. 2부터 40000까지 반복하면서 자기 자신만으로 밖에 나누어떨어지지 않는지 확인하면 되지만 시간이 오래 걸린다. 따라서 에라토스테네스의 체..

[백준] 17218번: 비밀번호 만들기

https://www.acmicpc.net/problem/17218 17218번: 비밀번호 만들기 첫째 줄과 둘째 줄에 수형이가 눈을 감고 만든 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는 최대 40자이다. 빈 문자열은 주어지지 않는다. 가장 긴 부분 문자열 www.acmicpc.net 전형적인 LCS (Longest Common Subsequence) 문제다. 그런데 최대 길이가 아닌 최대 공통 부분문자열을 출력해야 한다. 2개의 문자열이 주어지는데 하나를 y축, 다른 하나를 x축으로 하여 dp 배열을 아래와 같이 정의한다. #define MAXL 41 char str1[MAXL]; char str2[MAXL]; // dp[i][j] = str1의 i번째 문자와 str2의..

[백준] 17485번: 진우의 달 여행 (Large)

https://www.acmicpc.net/problem/17485 17485번: 진우의 달 여행 (Large) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2 ≤ N, M ≤ 1000)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 이전 이동 방향에 따른 dp 값을 계속 유지해야하는 것이 관건인 dp 문제다. 이 문제는 이동 방향이 딱 3가지인데, 같은 방향으로 2번 연속 움직일 수 없다는 것이 중요하다. 그렇다면 결국 이동 방향이 문제 해결의 핵심이란 말인데, 이전 이동 방향에 따라 최솟값을 모두 유지해야 하는 방향으로 구현을 해야 한다. 따라서 세로, 가로, 이전 방향을 모두 저장할..

[백준] 1354번: 무한 수열 2

https://www.acmicpc.net/problem/1354 1354번: 무한 수열 2 첫째 줄에 5개의 정수 N, P, Q, X, Y가 주어진다. www.acmicpc.net 배열이 아닌 해시테이블을 이용한 dp 문제다. N의 최댓값이 int 값을 벗어난다. 게다가 i 를 나누어서 범위를 한정지을 P와 Q조차 최솟값이 2이기 때문에 최악의 경우를 생각해보아도 dp 배열을 만들기에는 메모리가 남아나질 않을 것이다. 따라서 해시테이블을 이용하여 문제를 해결하기로 한다. 사실 해시테이블을 직접 구현하는 걸 선호하지만 귀찮으므로 그냥 unordered_map STL을 사용하기로 한다. #include typedef long long ll; // dp[a] = a를 key 값으로 하여 저장된 value u..

[백준] 3933번: 라그랑주의 네 제곱수 정리

https://www.acmicpc.net/problem/3933 3933번: 라그랑주의 네 제곱수 정리 입력은 최대 255줄이다. 각 줄에는 215보다 작은 양의 정수가 하나씩 주어진다. 마지막 줄에는 0이 하나 있고, 입력 데이터가 아니다. www.acmicpc.net 배낭 문제 비슷한 dp 문제다. 조금 생각하기 까다로웠다. 라그랑주의 네 제곱수 정리에 따르면, 모든 양의 정수는 4개 이하의 정수 제곱의 합으로 표현할 수 있다. 따라서 어떤 정수 N을 만들기 위해 필요한 제곱수의 개수를 저장해야 한다. dp 배열을 아래와 같이 정의한다. #define MAX_DIGIT 5 #define MAXN (1

[백준] 17265번: 나의 인생에는 수학과 함께

https://www.acmicpc.net/problem/17265 17265번: 나의 인생에는 수학과 함께 세현이의 인생의 목표는 1분 1초 모든 순간 수학과 함께 살아가는 것이다. 그렇기 때문에 매일 수학을 생각하면서 살아가고 있다. 세현이는 밥을 먹을 때도 쌀알의 수를 계산하여 칼로리를 바로 www.acmicpc.net 사칙연산과 관련된 dp 문제다. 탐색 범위가 최대 5 X 5 밖에 되지 않아서 완전탐색과 재귀가 떠오르긴 했지만 DP를 연습하는 목적으로 풀어보기로 한다. dp 배열을 아래와 같이 정의한다. #define MAXN 6 #define MAX 0 #define MIN 1 // dp[y][x][MAX] = (y, x) 까지 왔을 때의 최댓값 // dp[y][x][MIN] = (y, x) ..

[백준] 17845번: 수강 과목

https://www.acmicpc.net/problem/17845 17845번: 수강 과목 첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100,000), 필요한 공부시간 (1 ≤ T ≤ 10,000)이 www.acmicpc.net dp 문제 중 전형적인 배낭 문제다. dp 배열을 아래와 같이 정의한다. #define MAXN 10001 // dp[n] = n 시간일 때 얻을 수 있는 최대 중요도 int dp[MAXN]; 이 문제는 과목을 딱 1번만 선택할 수 있으므로 중복을 피해야 한다. 따라서 최대 가능한 시간부터 반대로 루프를 돌면서 최대 중요도를 업데이트 해준..