개발자의시작

문제링크 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 풀이 이번 문제 역시 DP로 풀기 좋은 문제입니다. 2xn 크기의 직사각형을 1x2 도형과 2x1도형을 사용하여 채우는 방법의 경우의 수를 구하는 문제입니다. 염두하여야 할 것은, 2xn 직사각형을 채울 때 2x1크기의 도형은 계속해서 쌓을 수 있지만 1x2크기의 도형은 두 개가 합쳐질 경우 2x2도형으로 만들어 쌓아야 하는 것입니다. 점화식을 유도하기 앞서 경우를 나열해보겠습니다. 설명의 편의를 위해 ..

문제링크 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net 문제 풀이 가장 전형적인 DP문제가 아닌가 생각됩니다. 각 계단에 도달할 때의 점수를 DP에 저장하는 방식으로 풀면 될 것 같습니다. 이 문제는 ..

문제링크 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 풀이 문제를 보자마자 딱 DP로 풀어야 할 것 같은 감이 드는 문제입니다. 반복 또는 재귀로 피보나치 함수를 구현하는 문제는 많이들 해보셨을 것 같습니다. 이 문제는 그중에서도 피보나치 함수의 재귀 호출 횟수를 계산하는 문제입니다. 피보나치 함수의 재귀 호출 자체가 DP가 되겠네요. 먼저 아래에 문제의 경우의 수를 표현해 보겠습니다. 인자가 0인 경우와 1인 경우는 미리 갖고 있는 것으로 가정하며, 맨 오른쪽 항에 있는 리스트 안에 숫자는 각각 Fibonacci(0)을 호출하는 ..

문제링크 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 문제 풀이 DP로 풀면 효과적으로 풀 수 있는 문제입니다. 정수 4를 1, 2, 3의 합으로 나타내는 방법의 수를 구..

문제링크 https://www.acmicpc.net/problem/18187 18187번: 평면 분할 무한한 크기의 이차원 평면에, 여러분은 최대 N개의 직선을 그릴 수 있다. 여러분은 기울기가 -1, 0, 1인 직선만 그릴 수 있다. 직선을 이용하여 평면을 최대 몇 개의 영역으로 분할할 수 있는지 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 풀이 좋아하는 TV 프로그램인 문제적남자에서 비슷한 문제를 본 적이 있는 것 같네요. 차이가 있다면 기울기가 -1, 0, 1인 직선만 그릴 수 있는 조건이 있습니다. 일단 저는 그리디로 접근했다가 DP로 풀이했습니다. 직선 개수를 늘려가면서 규칙을 찾았습니다. 직선 개수 분할된 면의 수 증가하는 개수 직선이 만나는 점의 수 1 2 +2 0 2 4..

문제링크 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 가장 기본적인 DP 문제입니다. 조건 3가지 (1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을뺀다) 를 사용해서 1을 만들기 위한 가장 적은 연산 횟수를 찾는 문제입니다. bottom-up(반복)을 통해서 문제를 풀었습니다. DP의 기본인 점화식을 세우면 아래와 같이 나타낼 수 있습니다. 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. -> D[N] = D[N/3]+1 2. X가 2로 나누어 떨어지면, 2로 나눈다. -> D[..