[백준] 1563번: 개근상

https://www.acmicpc.net/problem/1563 1563번: 개근상 백준중학교에서는 학기가 끝날 무렵에 출결사항을 보고 개근상을 줄 것인지 말 것인지 결정한다. 이 학교는 이상해서 학생들이 학교를 너무 자주 빠지기 때문에, 개근상을 주는 조건이 조금 독 www.acmicpc.net 이전의 상태를 고려해야 하는 dp 문제다. 지각을 누적 2번 하거나 결석을 연속 3번 하면 개근상을 받지 못 한다. 따라서 지각의 누적 횟수와 연속 결석 횟수를 저장하는 dp 배열을 만들어야 한다. dp 배열을 아래와 같이 정의한다. #define MAXN 1001// 전체 날짜 수 #define MAXL 2// 지각 가능 날짜 수 #define MAXA 3// 연속 결석 가능 날짜 수 #define DIVI..

[백준] 14852번: 타일 채우기 3

https://www.acmicpc.net/problem/14852 14852번: 타일 채우기 3 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 이전의 모양을 고려해서 해결하는 dp 문제다. 여느 타일 채우기 문제가 그렇듯... 특수한 경우를 생각해주면 되겠다. 우선 dp 배열을 아래와 같이 정의한다. #define MAXN 1000001 #define DIVIDER 1000000007 typedef long long ll; // dp[n] = (2 X n)을 채우는 경우의 수 ll dp[MAXN]; // sum[n] = dp[0] ~ dp[n] 까지의 누적합 ll sum[MAXN]; 정답 자체의 값은 int 범위를 넘지 않지만 연산 중의 값디 i..

[백준] 13302번: 리조트

https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 리조트를 방문할 수 있는 모든 날을 최소 비용으로 방문하는 dp 문제다. 1일권, 3일권, 5일권 티켓이 있고 3일권과 5일권을 구입하면 쿠폰을 각각 1개, 2개를 준다. 쿠폰 3개는 1일권 1장으로 사용할 수 있다. N일 중 방문할 수 있는 모든 날에 리조트를 방문한다고 할 때의 최소 비용을 구하는 문제다. 다른 분들은 보통 재귀로 풀었던데, 나는 dp 로 풀어보기로 했다. dp 배열을 아래와 같이 정의..

[백준] 10422번: 괄호

https://www.acmicpc.net/problem/10422 10422번: 괄호 ‘(‘, ‘)’ 문자로만 이루어진 문자열을 괄호 문자열이라 한다. 올바른 괄호 문자열이란 다음과 같이 정의된다. ()는 올바른 괄호 문자열이다. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 www.acmicpc.net 올바른 괄호 문자열을 만드는 경우의 수를 찾는 dp 문제다. dp 배열을 아래와 같이 정의한다. #define MAXN 5001 #define INF 1000000007 typedef long long ll; // dp[n] = 길이가 n 인 올바른 괄호 문자열의 개수 ll dp[MAXN]; 실제 출력되는 dp 의 값은 int 범위 안에 있으나, 연산 과정에서 int 범위를 넘어가는 경우가 발생..

[백준] 2602번: 돌다리 건너기

https://www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 이전에 밟은 글자와 다리를 고려해야 하는 dp 문제다. 이제 이런 문제를 볼 때마다, 다차원으로 dp 배열을 만들어야겠다는 생각부터 든다. 다리는 총 2개이며 번갈아 밟아야 한다. 글자는 최대 20글자이며, 반드시 순서대로 모두 밟아야 한다. 따라서 dp 배열을 아래와 같이 정의한다. #define MAXT 21// 밟아야 하는 문자열의 최대 길이 #define MAXL 101// 다리의 최대 길이 char..

[백준] 17069번: 파이프 옮기기 2

https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 이전의 방향을 고려해야 하는 dp 문제다. 문제에 따르면 파이프는 총 3가지 방향으로 움직일 수 있고 그 방향으로 움직이기 위해 장애물이 없어야 하는 범위도 정해져 있다. 파이프의 오른쪽 끝 부분만 중요하지, 다른 왼쪽 끝 부분은 고려할 필요가 없다. 따라서 파이프의 오른쪽 끝의 상태를 고려하며 dp 배열을 완성하면 된다. dp 배열을 아래와 같이 정의한다. #define..

[백준] 2631번: 줄세우기

https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net LCS 를 이용해서 해결하는 dp 문제다. 처음에는 문제 해결이 좀 막막했지만, LCS 를 이용하면 해결할 수 있을 것 같았다. LCS를 구하기 위해 dp 배열을 아래와 같이 정의한다. #define MAXN 201 // dp[n] = (1 ~ n)까지 LCS의 길이 int dp[MAXN]; int arr[MAXN]; // 수열이 저장된 배열 LCS 구하는 것은 지금까지 많이 해봤으니 쉬울 것이다. 현재..

[백준] 1915번: 가장 큰 정사각형

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 가장 큰 정사각형의 넓이를 구하는 dp 문제다. 처음에 누적합으로 가장 큰 정사각형의 넓이를 구하고자 했으나 시간이 오래 걸릴 것 같았다. 주어진 입력으로 0과 1밖에 들어오지 않으므로 간단히 dp로 풀어보기로 했다. dp 배열을 아래와 같이 정의한다. #define MAXN 1002 // dp[i][j] = (i, j)를 오른쪽 아래 꼭지점으로 하는 정사각형의 한 변의 최대 길이 int dp[MAXN][MAXN]; dp 배열을 정사각형 한 변의 최대 길이라고 했지만..

[백준] 9252번: LCS 2

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 주어진 두 문자열의 LCS 길이와 부분 수열을 출력하는 dp 문제다. LCS 길이를 추가로 출력하는 것 빼고, 앞서 포스팅한 문제와 완벽히 동일하다. 따라서 자세한 설명은 이 링크를 참고하는 것으로 대체한다. https://kalpaca.tistory.com/20 [백준] 17218번: 비밀번호 만들기 https://www.acmicpc.net/pr..

[백준] 10942번: 팰린드롬?

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 주어진 쿼리 구간이 팰린드롬인지 확인하는 dp 문제다. 일련의 수열이 주어지고 주어진 시작 부분부터 끝 부분까지 팰린드롬인지 확인해야 한다. 그런데 쿼리가 최대 100만개라서 매번 확인을 하면 시간 초과가 날 것이다. 따라서 dp 를 사용하기로 한다. 우선 dp 배열을 아래와 같이 정의한다. #define MAXN 2002 // dp[s][e] = (s ~ e) 구간이 팰린드롬이면 true, 아니면 false bool dp[MAXN][..