O'bin and the Chocolate Factory

링크>https://www.acmicpc.net/problem/9934  sol ) 재귀를 사용한 완전 이진트리 구성12345678910111213141516171819202122232425262728def makeTree(arr, level):    mid = len(arr) // 2    tree[level].append(arr[mid])        # arr의 원소가 1개이면 마지막 레벨이므로 return    if len(arr) == 1:        return        # level+1 한 후 왼쪽, 오른쪽 자식 노드 처리    makeTree(arr[:mid], level + 1)    makeTree(arr[mid + 1:], level + 1) def main():    k = i..

링크>https://www.acmicpc.net/problem/1926  sol 1 ) deque를 이용한 BFS로 풀이123456789101112131415161718192021222324252627282930313233343536373839404142import sysfrom collections import deque input = sys.stdin.readline dx = [-1, 1, 0, 0]dy = [0, 0, -1, 1] def bfs(x, y):    q = deque([(x, y)])    visited[x][y] = True    size = 1     while q:        x, y = q.popleft()        for i in range(4):            nx..

링크>https://www.acmicpc.net/problem/5525 123456789101112131415161718192021import sysinput = sys.stdin.read N = int(input().strip())M = int(input().strip())S = input().strip() answer, i, count = 0, 0, 0 while i  (M - 2):    if S[i:i+3] == 'IOI':        i += 2        count += 1        if count == N:            answer += 1            count -= 1    else:        i += 1        count = 0 print(answer)cs

링크>https://www.acmicpc.net/problem/1244  12345678910111213141516171819202122232425import sysinput = sys.stdin.readline N = int(input())        # 스위치 수switch = [-1] + list(map(int, input().split()))M = int(input())        # 학생 수 for _ in range(M):    student, num = map(int, input().split())    if student == 1:    # 남학생일 경우        for i in range(num, N+1, num):            switch[i] = 1 - switch[i]..

링크>https://www.acmicpc.net/problem/1629  123456789101112131415161718192021# 분할 정복(DAC)로 거듭제곱 계산하는 함수def dac(base, ex, mod):# base : 밑, ex : 지수, mod : 나누는 수     if ex == 0:        return 1    elif ex == 1:        return base % mod        # 분할 : 지수를 절반으로 나누기    half_ex = dac(base, ex//2, mod)    half_ex = (half_ex * half_ex) % mod     # 지수가 홀수인 경우 추가 계산    if ex % 2 == 0:        return half_ex    ..

링크>https://www.acmicpc.net/problem/1149   123456789101112n = int(input())arr = [list(map(int, input().split())) for _ in range(n)] dp = [[0]*3 for _ in range(n)]dp[0] = arr[0] for i in range(1, n):    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0]    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1]    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + arr[i][2] print(min(dp[n-1]))Colored by Color Sc..

링크>https://www.acmicpc.net/problem/11053  sol ) 다이나믹 프로그래밍으로 가장 긴 증가하는 수열 구하기12345678910111213n = int(input())a = list(map(int, input().split())) dp = [0 for _ in range(n)] for i in range(n):    for j in range(i):        if a[i] > a[j] and dp[i]  dp[j]:            dp[i] = dp[j]    dp[i] += 1    #print(i, dp)    print(max(dp))cs line 6 ) 배열 a의 i번째 원소를 기준으로line 8 ) i번째 원소가 j번째 원소들보다 크고(=증가하는 수열) a..

링크>https://www.acmicpc.net/problem/23057   sol )  combinations로 조합을 뽑고, set에 합 저장12345678910111213from itertools import combinations n = int(input())nums = list(map(int, input().split()))m = sum(nums) sums = set() for i in range(1, n+1):    for j in combinations(nums, i):        sums.add(sum(j)) print(m - len(sums))cs set()를 사용해 중복을 고려하지 않고 모든 조합의 합을 저장한다.m에서 sums의 길이를 빼면 만들어지지 않은 수의 개수를 얻게 된다.

링크>https://www.acmicpc.net/problem/2910 주어진 수열을 빈도, 출현순서 순으로 정렬하여 출력  sol 1) 딕셔너리에 저장 후 람다식으로 정렬 (72ms)1234567891011121314from collections import defaultdict n, c = map(int, input().split())nums = list(map(int, input().split())) dic = defaultdict(int)for i in nums:    dic[i] += 1 sorted_dic = sorted(dic.items(), key = lambda x: (-x[1], list(dic.keys()).index(x[0]))) for i, j in sorted_dic:    fo..

링크>https://www.acmicpc.net/problem/2579  123456789101112131415161718192021222324252627import sysinput = sys.stdin.readline n = int(input()) stairs = [0] * 301for i in range(1, n + 1):    stairs[i] = int(input()) if n == 1:    print(stairs[1])    exit(0) elif n == 2:    print(stairs[1] + stairs[2])    exit(0)  dp = [0] * 301dp[1] = stairs[1]dp[2] = stairs[1] + stairs[2]dp[3] = max(stairs[1] + sta..