[Python] 백준 알고리즘 온라인 저지 11727 2×n 타일링 2 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 11726번의 후속 문제로 2x2타일이 추가되었다. 풀이 방법은 11726번 2×n 타일링 파이썬 풀이과 동일하게 동적 계획법과 점화식을 이용하여 풀이하였습니다. 코드 import sys input = sys.stdin.readline n = int(input()) dp = [0, 1, 3, 5] for i in range(4, n+1): dp.append..
[Python] 백준 알고리즘 온라인 저지 11726 2×n 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net DP(동적 계획법)과 점화식을 이용하여 풀어야 하는 문제로 먼저 작은 수들의 경우의 수를 구해 이를 활용하여 코드를 작성하였다. 코드 import sys input = sys.stdin.readline n = int(input()) dp = [0, 1, 2, 3] for i in range(4, n+1): dp.append((dp[i-1] + (dp[..
[Python] 백준 알고리즘 온라인 저지 1463 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 동적 계획법을 이용해 풀어야 하는 문제로 재귀 같은 경우도 어렵다고 느꼈지만 이번 문제도 어렵다고 느꼈다. 3이나 2로 나눠지면 나누거나 1을 빼서 1로 만드는 최소한의 경우의 수를 구해야 하는 문제였다. 이 문제에서 DP를 사용하는 이유는 이전 경우의 수들의 값을 이용하기 위해 계산결과를 저장하고 그 값을 이용하기 위함이다. 코드 import sys import math input = sys.stdin.readline def dp(): x = i..
🚀 새로운 블로그로 이전했습니다.
살펴보러 가기
