문제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]) ..

문제 https://www.acmicpc.net/problem/12101 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net 풀이 n,k = map(int,input().split()) save = {} save[1] = ["1"] save[2] = ["1+1","2"] save[3] = ["1+2","1+1+1","2+1","3"] for i in range(4,12): save[i] = [] for j in save[i-1]: save[i].append(j+"+1") for j in save[i-2]: save[i].append(j+"+2") ..

문제 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 a = [int(input()) for i in range(int(input()))] target = max(a) save = [1] * (target + 1) save[1] = 1 save[2] = 2 save[3] = 4 for i in range(4,target+1): save[i] = (save[i-1] + save[i-2] + save[i-3])%1000000009 for i in a: print(save[i]%100000000..

문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 a = [] for _ in range(int(input())): s,e = map(int,input().split()) a.append((s,e)) a.sort(key=lambda x: (x[1],x[0])) count = 0 now = 0 for t in a: if t[0] >= now: count += 1 now = t[1] print(count) 그리디 알고리즘 문제이다. 회의가 끝나는 시간을 기준으로 정렬하고(끝나는 시간이 같다면 시작하는 시간이 작은거부터 정렬) 이전 회의가 끝나기 이전에 시..

문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 풀이 n = int(input()) memo = {} memo[1] = 1 memo[2] = 1 memo[3] = 1 memo[4] = 2 memo[5] = 2 def a(i): if i not in memo: memo[i] = a(i-1) + a(i-5) return memo[i] for i in range(n): print(a(int(input()))) 단순한 DP 문제이다. N이 1~5일때는..