Algorithm

오늘은 DP 문제 중 2xn 타일링 2편 문제를 풀어봅시다. 11727 결과 : 맞았습니다!! 풀이 시간 : 1시간 미만 성공 풀이 과정 2xn 타일링 1편 문제와 마찬가지로 패드를 이용하여 2x4 크기의 직사각형까지 그려서 규칙을 알아내고자 했습니다. 찾은 규칙은 다음과 같습니다. 전 단계의 직사각형에 추가로 2x1 직사각형을 그립니다. 두 단계 이전의 직사각형에 추가로 직사각형을 그립니다. 1x2 직사각형 2개 2x2 직사각형 1개 따라서 a[n] = a[n-1] + a[n-2] * 2입니다. 코드 비교 나의 코드 (PyPy3) n = int(input()) memory = [0, 1, 3] for i in range(3, n+1): memory.append(memory[i-2] * 2 + memor..

오늘은 DP 문제 중 2xn 타일링 1편 문제를 풀어봅시다. 11726 문제 : https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 결과 : 맞았습니다!! 풀이 시간 : 1시간 미만 성공 풀이 과정 패드를 이용하여 2x4 크기의 직사각형까지 그려서 규칙을 알아내고자 했습니다. 전 단계의 직사각형에 추가로 2x1 직사각형을 그리고, 두 단계 이전의 직사각형에 추가로 1x2 직사각형 2개를 그리면 되는 규칙이 나오게 되었습니다. 따라서 a[n] = a[n-2] + a[n-..

오늘은 DP 문제 중 하나인 백준 1463번 문제를 풀어봅시다. 1463 문제 : https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 결과 : 맞았습니다!! 풀이 시간 : 1시간 미만 성공 코드 비교 나의 코드 (PyPy3) import sys from collections import deque input = sys.stdin.readline n = int(input()) memory = {} queue = deque([(n, 0)]) while queue: now, score = queue.popleft() if now in memory and memory[..