연잎의 develog

11726번: 2×n 타일링 (acmicpc.net) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net [문제] 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. [해결전략] : 본문제가 처음부터 dp로 풀어야하는 문제라는 것을 알아차리기는 쉽지 않다. n의 크기를 하나씩 늘려가며 직접 경우의 수를 세보면, 규칙성이 발견된다! 그 규칙을 이용해 점화식을 세워주면 dp로 쉽게 해결할 수 있다. 1. 테이블 정의하기 dp[i] = 2 x i 크기의 직사각형을 채우는 방법의 수 2. 점화식 ..

2579번: 계단 오르기 (acmicpc.net) 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net [문제] [해결전략] 만일 n이 그다지 크지 않았다면, 백트래킹과 같은 방식으로 O(2^N)만에 해결이 가능하지만 지금 처럼 N이 300일때는 어림도 없다 따라서 DP 를 통해 해결해주어야한다. 1. 테이블 정의하기 dp [i] = i번째 계단까지 올라섰을 때 점수 합의 최댓값 만일 위와 같이 테이블을 정의하게 되면 연속한 세계단을 모두 밟을 수 없다는 제약조건을 점화식에 넣을 방법이 없다..! 따라서 테이블을 다른 방식으로..

9095번: 1, 2, 3 더하기 (acmicpc.net) 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net [문제] 수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오 [해결전략] 1. 테이블 정의하기 dp [i] = 정수 i 를 1,2,3 의 합으로 나타내는 경우의 수 2. 점화식 찾기 한번에 점화식을 찾기는 어려우므로 한번 실제 숫자를 대입시켜서 예시와 함께 생각해보자!..

1463번: 1로 만들기 (acmicpc.net) 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net [문제] [해결전략] 사실 이문제는 해결한 적이 있다. 처음에 이문제를 bfs 로 풀었었는데 오늘은 dp로 한번 더 풀어보려고한다! dp 문제는 보통 4단계로 해결할 수 있다. 1. 테이블 정의하기 dp [i] = i를 1로 만들기 위해 필요한 연산 횟수의 최솟값 2. 점화식 찾기 한번에 점화식을 찾기는 어려우므로 한번 실제 숫자를 대입시켜서 예시와 함께 생각해보자! dp [1] ~ dp[11] 의 값을 모두 알고 있는 상황에서 dp[12] 의 값을 구해야한다면? 3으로 나누거나 (dp [12] = dp[4] + 1 ) 2으로..

1149번: RGB거리 (acmicpc.net) 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net [문제] RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지..