백준 : 동적 프로그래밍

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net import sys input = sys.stdin.readline # 입력을 빠르게 받기 위해 sys.stdin.readline 사용 n = int(input()) # 격자의 크기 입력 받기 map = [list(map(int, input().split())) for _ in range(n)] # 격자 정보 입력 받기 dp = [[[0, 0, 0] for _ in ran..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 이문제는 간단한 문제이다 2로 나누어지면 2로 나누고, 3으로 나누어지면 3으로 나눈다. 2, 3으로 나누어지지 않으면 1을 빼준다. 위 과정을 반복해서 최소 연산의 수를 구하면 되는 문제이다. 바로 코드를 살펴보자 import java.util.Scanner; public class 일로만들기 { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] dp = new int[N ..

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 피보나치 함수의 입력값이 주어졌을 때 0과 1이 몇번호출 되었는지 개수를 구하는 문제이다. 입출력을 살펴보자. 예제 입력 1 복사 3 0 1 3 3개의 n값 0,1,3을 입력받아 0과 1의 개수를 출력하면 된다. 0 -> 당연히 0호출 0 ->1, 0 1 -> 당연히 1호출 0 -> 0, 1 3 -> 2, 1 호출 -> 2가 다시 1,0호출 -> 1, 2 위 계산을 보면 점화식이 보인다. dp[i] = dp[i - 1] + dp[i - 2] 점화식이 나왔으니 바로 코드를 짜보자. 시간 초과 코..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 배열의 크기 N, 배열 dp[]가 주어졌을 때 가장 긴 바이토닉 수열의 값을 구하는 문제이다. 예제를 살펴보자 dp의 값은 이전값이 현재값보다 작을 때 + 1을 해주면된다. 바이토닉 수열의 최댓값을 구하기 위해서는 dp[]배열의 (왼쪽 -> 오른쪽) + (오른쪽 -> 왼쪽)을 해서 최댓값을 출력해주면 된다. 그러므로 우린 dp[]를 입력 받고 좌 -> 우를 순환하여 수열의 값을 찾고, 우 -> 좌를 순환하여 수열을 ..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 제목그데로 숫자 N이 주어졌을 때 N의 제곱수들의 합인 최솟값을 구하는 문제이다. 위에 적은 제곱수들이 주어진 N에 대한 최솟값의 제곱수들로 이루어진 수이다. 예제를 분석해보았다. public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); ..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 LCS 시간 제한메모리 제한제출정답맞힌 사람정답 비율 0.1 초 (하단 참고) 256 MB 74123 30211 22201 40.305% 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CA..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보는 문제이다. (0으로 시작하는 수는 계단수가 아니다.) 문제풀이 문제을 보면 N자리수의 계단수가 몇개인지 구하면 되는 dp 문제이다. 문제를 직관적으로 보기위해 n = 1, 2, 3 일 경우에 표를 작성해보려한다. 위 표를 보고 규칙성을 찾아보려한다. 0 구간 범위에서 오른쪽 대각선 dp[i-1][1]을 저장하고 9 구간 범위에서 왼쪽 대각선 dp[i-1][8]을 저장하고 1 ~ 8 구간의 범위에서 (dp[i-1][j-1] + dp[i-1]..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 이문제는 첫 줄에서 물품의 수 N, 버틸 수 있는 무게 K를 입력받은 뒤 물품의 무게 W를 고려하여 물건의 가치 V의 최댓값을 구하는 문제이다. 문제풀이 이문제를 이해하기위해 예제의 입력값과 출력값을 표를 통해 직관적으로 분석해보려한다. 물품의 수 N = 4 버틸 수 있는 무게 K = 7 물건의 무게 W = 6, 4, 3, 5..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 문제 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복사 3 예제 입력 2 복사 8 예제 출력 2 복사 171 예제 입력 3..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 ..