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

[백준] 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번 이 된다. ..