문제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/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일때는..

문제 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 풀이 n,k = map(int,input().split()) name = list(map(int,input().split())) tap = [0] * n i=0 answer = 0 while i 그냥 패스 2) 빈자리가 있는경우 -> 해당 자리에 꽂기 3) 빈자리가 없는경우 -> 가장 나중에 다시 사용될 제품의 코드를 뽑기, answer에 1 더하기 위 과정을 반복하여 모든 전자용품이 사용되..

문제 https://www.acmicpc.net/problem/11283 11283번: 한글 2 한글의 각 글자는 초성, 중성, 종성으로 이루어져 있고, 이 세 가지를 모아써서 한 글자를 나타낸다. 초성은 ㄱ, ㄲ, ㄴ, ㄷ, ㄸ, ㄹ, ㅁ, ㅂ, ㅃ, ㅅ, ㅆ, ㅇ, ㅈ, ㅉ, ㅊ, ㅋ, ㅌ, ㅍ, ㅎ로 총 19개가 있 www.acmicpc.net 풀이 print(ord(input())-44031) 아주아주 간단한 코드 한줄이다. 파이썬은 ord를 이용하여 유니코드 번호를 알아낼 수 있다. '가'의 유니코드가 44032 이고 1번째 한글이므로, 입력받은 문자의 유니코드에 44031을 빼주어서 출력하면 순서를 알 수 있다.