[백준] 14002번: 가장 긴 증가하는 부분 수열 4

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 전형적인 LIS (Longest Increasing Subsequence) 문제인데, 그 수열까지 출력하는 dp 문제다. 여느 LIS 문제처럼 dp 배열을 아래와 같이 정의한다. #define MAXN 1001 // dp[n] = 1 ~ n 번째 수열 중 가장 긴 증가하는 부분 수열의 길이 int dp[MAXN]; ..

[백준] 2133번: 타일 채우기

https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 타일의 모양에 따른 모든 경우의 수를 계산하는 dp 문제다. 이 문제는 (1 X 2), (2 X 1) 모양의 타일로 (3 X N) 을 채우는 모든 경우의 수를 구하는 문제다. dp 배열을 아래와 같이 정의한다. #define MAXN 31 // dp[n] = (3 X n) 까지 채울 수 있는 모든 경우의 수 int dp[MAXN]; 만약 N이 홀수라면 가능한 경우는 반드시 0이 된다. 총 3가지 경우로 나누어 생각할 수 있다. 1) N = 0 - 문제 조건은 아니지만, dp[0] = 1 로 설정한다. 2) ..

[백준] 11054번: 가장 긴 바이토닉 부분 수열

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 증가하는 부분 수열 + 감소하는 부분 수열을 합친 듯한 dp 문제다. 바이토닉 부분 수열이란, 증가 → 감소 하는 부분 수열을 의미한다. 반드시 연속될 필요는 없으며, 증가 → 감소 → 증가 같은 경우는 해당하지 않는다. 이 문제는 증가하는 부분 수열의 길이를 2번 구함으로써 해결할 수 있다. 먼저 증가하는 부분 수열의 길이를 구하기 위해 dp 배열 2개를 아래와 같이 정의한다. #define MAXN 1001 in..

[백준] 22115번: 창영이와 커피

https://www.acmicpc.net/problem/22115 22115번: 창영이와 커피 커피는 종류별로 하나씩 준비되어 있기 때문에, 동일한 커피를 여러 개 마실 수 없음에 유의하라. www.acmicpc.net 최솟값을 구하는 배낭 문제 중 하나인 dp 문제다. https://kalpaca.tistory.com/15 [백준] 17845번: 수강 과목 https://www.acmicpc.net/problem/17845 17845번: 수강 과목 첫줄에 서윤이의 최대 공부시간 N (1 ≤ N ≤ 10,000), 과목 수 K (1 ≤ K ≤ 1,000)이 공백을 사이에 두고 주어진다. 이후 K개의 줄에 중요도 I (1 ≤ I ≤ 100 kalpaca.tistory.com 정확히 K를 맞추는 것과 최솟..

[백준] 13910번: 개업

https://www.acmicpc.net/problem/13910 13910번: 개업 해빈이는 짜장면을 정말 좋아한다. 짜장면을 너무 좋아한 나머지 짜장면만 파는 중국집을 개업했다! 해빈이는 양손잡이여서 동시에 두 개의 웍(중국 냄비)을 사용하여 요리할 수 있다. 그러나 www.acmicpc.net 동시성을 고려해야 하는 배낭 문제의 변형인 dp 문제다. 최대 2개의 웍을 사용해서 N 그릇을 만드는 데 필요한 최소 요리 횟수를 구하는 문제다. 여타 다른 배낭 문제와 컨셉은 비슷한데 동시성이라는 조건이 들어간다. 예를 들어 1 그릇과 3 그릇용 웍이 있다면, 4그릇을 만들기 위해 1 그릇 요리 + 3 그릇 요리 = 2번 이 아니라 왼손으로 1 그릇 요리 && 오른손으로 3 그릇 요리 = 1번 이 된다. ..

[백준] 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의..