본문 바로가기

Algorithm/Dynamic Programming

 (32)
[C++] 백준 2156번 : 포도주 시식 (S1) #문제 www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net #풀이 & 학습한 내용 supremo7.tistory.com/88에서 푼 이친수 문제와 유사한 문제이다. 이 문제는 경우를 크게 3가지로 나눠 문제를 관찰했다. 마신것을 1, 안마신것을 0이라 할 때, i-1번째와 i번째의 경우를 ?0,01,11로 나누었다.(?0은 00과 10을 모두 포함한다) 이때, 각각의 경우를 dp배열의 index 0, 1, 2에 저장하여 각각의 optimization을 관찰했다. ..
[C++] 백준 9465번 : 스티커 (S2) #문제 www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net #풀이 & 학습한 내용 supremo7.tistory.com/100에서 풀었던 동물원 문제와 매우 유사한 문제이다. 한 열을 기준으로 위아래가 모두 비어있는 경우 index 0에, 위에만 있는 경우 index 1에, 아래에만 있는 경우 index 2에 각각의 optimization을 저장한다. 동물원에서는 경우의 수를 구했다면, 이 문제에서는 최대합을 구한다. 소스코드의 25~27행에 해당하는..
[C++] 백준 11057번 : 오르막 수 (S1) #문제 www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net #풀이 & 학습한 내용 소스코드의 16~22행에 해당하는 Optimal substructure를 통해 for문을 구성합니다. 마지막에 오는 원소가 i일 때 그 직전에 오는 수가 0부터 i까지 가능함을 이용합니다. dp[i][j]를 i번째수가 j일때의 경우의 수라 할때 dp[i][j]는 dp[i-1][0]부터 dp[i-1][j]까지의 합입니다. #소스코드 1 2 3 4 ..
[C++] 백준 1309번 : 동물원 (S1) #문제 www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net #풀이 & 학습한 내용 x가 빈공간, o가 사자가 있는공간이라 할 때, 한 줄에서 가능한 경우는 xx, ox, xo이다. 그리고 이 각각의 경우에 대해 optimization을 살펴본다. dp[i][0]을 i번째 줄이 xx일 때, 총 경우의 수, dp[i][1]을 i번째 줄이 ox일 때, 총 경우의 수, dp[i][2]을 i번째 줄이 xo일 때, 총 경우의 수라 하자. 이때 코드의 13~15행에 해당하는 optimal substructure를 통해 for문으로 dp배열을 채워나간다. #소스코드 1 2 3 4 5 6 7 8 9 10 11 ..
[C++] 백준 1149번 : RGB거리 (S1) #문제 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net #풀이 & 학습한 내용 각각의 집에 대해 빨강, 초록, 파랑으로 칠했을 때의 Optimization(이 문제에선 비용의 최솟값)을 따로 살펴본다. 그리고 dp[i][0]을 "i번째 집을 빨강으로 칠했을 때의 첫번째 집부터 i번째 집까지의 비용합의 최솟값"으로 정의한다. dp[i][1], dp[i][2]는 앞의 정의에서 빨강을 초록, 파랑으로 바꾸어 생각한다. 아래 코드의 18~20행..
[C++] 백준 9252번 : LCS 2 (G5) #문제 www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net #풀이 & 학습한 내용 앞서 풀이한 supremo7.tistory.com/97에서 LCS 자체를 추가로 출력해줘야 하는 문제이다. 이를 위해 동선을 역추적하는 배열을 따로 선언하고 재귀를 통해 동선을 출력해준다. if문에서 ==를 =로 적는 실수 하지말자 #소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ..
[C++] 백준 9251번 : LCS (G5) #문제 www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net #풀이 & 학습한 내용 index가 0부터 시작하게 설정한 것이 있고, 1부터 시작하게 설정한 것이 있어 확실히 정리해두고 코딩하지 않으면 매우 헷갈린다. 두 문자열의 마지막을 기준으로 생각하여 경우를 나누고 optimal substructure를 구해서 for문을 통해 구현했다. strlen을 사용하기 위해 #inlcude을 추가해줬다. #소스코드 1 2 3..
[C++] 백준 2225번 : 합분해 (G5) #문제 www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net #풀이 & 학습한 내용 dp배열은 long long으로 선언했지만, sum을 int로 선언하여 "틀렸습니다"가 나왔다. int의 최댓값 약 2,000,000,000을 기억하자. 합하는 과정에서 int의 범위를 넘을 수 있으므로 sum도 long long으로 선언해주어야 한다. 또한 모듈로 법칙인 (A+B)%C=(A%C+B%C)%C 또한 잊지말자. dp[i][j]를 "0~i까지의 정수 j개를 더해 i를 만드는 경우의 수"라 하고, dp[30][3]과 같은 경우를 예로 들어 dp배열을 어느순서로 채울지 먼저 파악한다. 그리고 그 순서..

티스토리툴바