[백준] 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번만 선택할 수 있으므로 중복을 피해야 한다. 따라서 최대 가능한 시간부터 반대로 루프를 돌면서 최대 중요도를 업데이트 해준..

[백준] 1577번: 도로의 개수

https://www.acmicpc.net/problem/1577 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자 www.acmicpc.net 끊어진 도로를 어떻게 표현하는지가 관건인 dp 문제다. 문제에서 최단 거리로만 이동한다고 하였으므로 좌상단에서 우하단으로 이동하기 위해 오른쪽 또는 아래쪽으로만 이동이 가능하다. 따라서 dp 배열은 위의 경우와 왼쪽 경우를 더한 값을 저장해두면 된다. 계산을 편리하게 하기 위해, 맨 위와 맨 왼쪽을 0으로 padding 하여 구현한다. dp 배열을 아래와 같이 정의한다. #defi..

[백준] 3067번: Coins

https://www.acmicpc.net/problem/3067 3067번: Coins 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 모든 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어 30원을 만들기 위해 www.acmicpc.net dp 중 전형적인 배낭 문제다. dp 배열을 아래와 같이 정의한다. #define MAXM 10001 #define MAXN 21 // dp[m] = m원을 만들 수 있는 모든 경우의 수 int dp[MAXM]; int coin[MAXN; coin 배열에는 사용할 수 있는 동전의 액수가 들어간다. 점화식을 구하기 위해 base 조건과 귀납적 정의를 알아본다. 1) n = 0 ..

[백준] 2591번: 숫자카드

https://www.acmicpc.net/problem/2591 2591번: 숫자카드 1부터 34까지 수가 적힌 카드가 충분히 많이 있다. 이들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적었다. 예를 들어 아래와 같이 카드가 놓인 경우 숫자를 차례로 적으면 27123이 된다. 나중 www.acmicpc.net 숫자의 범위를 생각해서 해결하는 dp 문제다. dp 배열을 아래와 같이 정의한다. #define MAXN 42 // dp[n] = str[0] ~ str[n-1] 까지의 모든 경우의 수 // dp 배열은 1부터 시작하는 것으로 구현 int dp[MAXN]; char str[MAXN]; 우리가 생각해야할 조건은 크게 2가지다. 1) n번째 숫자를 1자리 수로 생각하는 경우 2) n-1번째, ..

[백준] 2410번: 2의 멱수의 합

https://www.acmicpc.net/problem/2410 2410번: 2의 멱수의 합 첫째 줄에 경우의 수를 출력한다. 답이 커질 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 점화식을 구상해서 해결하는 dp 문제다. dp 배열을 아래와 같이 정의한다. #define MAXN 1000001 #define DIVIDER 1000000000 // dp[n] = n을 2의 멱수로 나타낼 수 있는 경우의 수 int dp[MAXN]; 점화식을 세우기 위해 오름차순으로 몇 가지 케이스를 생각해 본다. 1) 1 = 1 (base) 2) 2 = 1+1 / 2 3) 3 = 1+1+1 / 1+2 4) 4 = 1+1+1+1 / 1+1+2 // 2+2 / 4 5) 5 ..

[백준] 2229번: 조 짜기

https://www.acmicpc.net/problem/2229 2229번: 조 짜기 알고스팟 캠프에 N(1 ≤ N ≤ 1,000)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는데, 어느 날 조별 수업을 진행하기로 하였다. 조별 수업의 목적은 잘 하는 학생들과 덜 잘 하는 www.acmicpc.net 최대 최소를 이용한 DP 문제다. dp 배열을 아래와 같이 정의한다. #define MAXN 1001 // dp[n]: 1 ~ n번째 학생까지 조를 나눴을 때의 가장 높은 값 int dp[MAXN]; n번째 학생을 추가했을 때의 가장 높은 값은 아래 경우 중의 최댓값으로 구할 수 있다. 1) dp[n-1] + (n) 번째 학생 1명인 조의 값 2) dp[n-2] + (n-1, n) 번째 학생..