문제출처] https://www.acmicpc.net/problem/9184 문제요약 재귀 함수를 다이나믹 프로그래밍으로 구현하기 풀이 식이 모두 주어줘 있는 재귀 함수이므로 다이나믹 프로그래밍만 구현해주면 된다. 다이나믹 프로그래밍에서 가장 중요한 점은 "이미 계산했던 값은 다시 계산하지 않는다."이다. 그래서 dp라는 리스트를 만들어 계산했던 값은 저장해 주면 된다. dp 리스트를 선언할 때 인풋값의 범위가 -50 ~ 50 이므로 사이즈를 102로 하였다. 음수값이 들어오더라도 리스트의 뒤의 값부터 인덱싱을 하기 때문에 추가적인 코드를 짤 필요는 없다. 소스코드는 Python 3으로 작성되었습니다. import sys input = sys.stdin.readline dp = [[[False for _..

문제출처] https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제요약 다이나믹 프로그래밍을 통하여 문제 풀이. 풀이 dp 배열에 테이블의 점수를 다이나믹 프로그램을 통하여 담으면 된다. dp는 인덱스가 하나 증가할 때마다 최대값을 담아댜 된다. 소스코드는 Python 3으로 작성되었습니다. n = int(input()) table = [[0,0] for i in range(20)] dp =[0]*20 for i in range(1,n+1): table[i][0], table[i][1] = [int(a) for a in input().split()] for i in range(1, n..

문제링크] https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. www.acmicpc.net 문제요약 2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 문제입니다. 백준 11726 문제와 마찬가지로 다이나믹 프로그래밍을 이용한 알고리즘 문제이다. 2019/07/30 - [컴퓨터/알고리즘] - [백준] 11726 2 x n 타일링 [백준] 11726 2 x n 타일링 문제링크] https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프..

문제링크] https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제요약 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 문제입니다. 풀이 다이나믹 프로그래밍 알고리즘 문제를 풀기 위해서는 점화식을 구하는 것이 가장 중요하다. (가로가 n일 때 타일을 채우는 경우의 수) = (가로가 n-1 일 때 타일을 채우는 경우의 수) X (1만큼 가로가 증가했을 때 타일을 채우는 경우의 수) + (가로가 n-2 일 때 타일을 채우는 경우의 수) X (2만..