본문 바로가기

다이나믹 프로그래밍

(4)

DP(다이나믹 프로그래밍): 백준 11726 파이썬 문제: https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 풀이: 이 문제는 다이나믹 프로그래밍의 기초 예제에서 빠질 수 없는 타일링 문제 유형이다. 다이나믹 프로그래밍 문제에서는 종종 결과를 어떤 수로 나눈 결과를 출력하라는 내용이 들어가 있는 경우가 많다. 이 문제에서도 10007로 나눈 나머지를 출력하라고 하는데, 이는 단지 결괏값이 굉장히 커질 수 있기 때문에 그런 것이다. 따라서 값을 계산할 때마다 특정한 수로 나눈 나머지만 취하도록 하면 된다. 왼쪽부터 차례..

DP(다이나믹 프로그래밍): 백준 9095 파이썬 1,2,3 더하기 문제: https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이: 이 문제를 풀면서 어떻게 점화식을 세워야 하는지에 대한 고민을 1시간 정도 했었는데 잘 떠오르지 않아 결국 구글링을 했다. 규칙은 아주 간단했다. 점화식을 찾아서 해결하는 전형적인 DP문제였다. 1 -> (1), 1개 2 -> (1+1), (2) 2개 3 -> (1+1+1), (1+2), (2+1), (3) 4개 4 -> (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), .... 7개 5 -> (1+1+1+1+1), .... 13개 위의 규칙을 봤을 때, 정수 4..

DP: 백준 11052 파이썬 카드 구매하기 문제: https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이: 카드 n개를 구매하면서 가장 비싸게 구매하는 금액을 출력하는 문제이다. 각 경우를 생각해보자. 카드 1개 살 때: 0 + 1 카드 2개 살 때: 0 + 2 1 + 1 카드 3개 살 때: 0 + 3 1 + 2 카드 4개 살 때; 0 + 4 2 + 2 1 + 3 금액 들을 dp 배열에 저장하고 배열의 최댓값을 출력해주면 된다. 정답: import sys input = sys.stdin.read..

DP(다이나믹 프로그래밍): 백준 11727 파이썬 문제: https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이: 이 문제는 11726번 문제 '2 x n 타일링'에서 타일 하나를 더 추가한 문제이다. 2021.09.12 - [Python 코딩테스트] - DP(다이나믹 프로그래밍): 백준 11726 파이썬 DP(다이나믹 프로그래밍): 백준 11726 파이썬 문제: https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를..

이전 1 다음

티스토리툴바