문제https://www.acmicpc.net/problem/1463풀이n = int(input())memo = [0]*(n+1)for i in range(2,n+1): k=[memo[i-1]] if i%3==0: k.append(memo[i//3]) if i%2==0: k.append(memo[i//2]) memo[i] = min(k)+1print(memo[n]) 다이나믹 프로그래밍(DP) 문제이다.연산을 통해 n을 1로 만든다는 생각 보다는1부터 시작해서 n으로 만든다는 생각으로 풀이하였다. 어떤수 n을 만들기 위해 필요한 연산의 가짓 수는 총 3가지를 고려해야한다.1. n/3를 만드는데 필요한 연산 수 +1 (n이 3으로 나누어 떨어질 때)2. n/2를..

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 n = int(input()) numbers = list(map(int,input().split())) memo = [0]*n for i in range(n): target = [0] for j in range(i): if numbers[j] < numbers[i]: target.append(memo[j]) ..