지식보부상님의 공부 일지

https://www.acmicpc.net/problem/11726 # 백준 11726번: 2xn 타일링# 다이나믹 프로그래밍 (실버 3)n = int(input())cntList = [0] * max(3, (n+1)) # cntList[i]: 2xi 크기 직사각형을 1x2, 2x1 타일로 채우는 방법의 수cntList[1] = 1cntList[2] = 2# cntList[i] = cntList[i-1]+cntList[i-2]for i in range(3, n+1): cntList[i] = cntList[i-1]+cntList[i-2]print(cntList[n] % 10007) 문제2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×..

https://www.acmicpc.net/problem/1463# 백준 1463번: 1로 만들기num = int(input())cntList = [0] * (num+1)for i in range(2, num+1): if i % 3 == 0: if cntList[i//3] 문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다..

책의 예제 문제에 대한 제 답안을 작성한 게시글 입니다.CHATER 03 그리디P.99내 코드n, k = map(int, input().split())result = 0while True: if n % k == 0: n = n // k result += 1 else: n -= 1 result += 1 if n == 1: breakprint(result)하지만 이는 n의 값이 커지면 1을 빼는 연산에서 시간이 걸리므로, 다음과 같이 연산을 개선할 수 있다. n, k = map(int, input().split())result = 0while True: target = (n // k) * k # k로 나누어떨어질 수 있..

책의 예제 문제에 대한 제 답안을 작성한 게시글 입니다.CHATER 03 그리디P.96내 코드N, M = map(int, input().split())min_card = []for i in range(N): cards = list(map(int, input().split())) min_card.append(min(cards))min_card.sort(reverse=True)print(min_card[0])

책의 예제 문제에 대한 제 답안을 작성한 게시글 입니다.CHATER 03: 그리디P. 92제출 코드N, M, K = map(int, input().split())number_list = list(map(int, input().split()))number_list.sort(reverse=True)# 반복되는 묶음의 개수sets_cnt = M // (K + 1)# 반복되고 남은 부분의 개수sets_rest = M % (K + 1)ans = (number_list[0] * K + number_list[1]) * sets_cntans += sets_rest * number_list[0]print(ans)

https://www.acmicpc.net/problem/15989  제출 코드test_case = int(input())for _ in range(test_case): n = int(input()) cnt_3 = n // 3 cnt = 0 for i in range(0, cnt_3 + 1): cnt += (n - 3 * i) // 2 + 1 print(cnt)

제출 코드def backtrack(n, m, cur): if len(cur) == m: print(*cur) return for i in range(1, n+1): cur.append(i) backtrack(n, m, cur) cur.pop() n, m = map(int, input().split())backtrack(n, m, [])문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 M개를 고른 수열같은 수를 여러 번 골라도 된다.입력첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)출력한 줄에 하나씩 문제의 조건을 만족하..

알고리즘 분류백트래킹제출 코드def backtrack(s, n, m, cur): if len(cur) == m: print(*cur) return for i in range(s, n+1): if i not in cur: cur.append(i) backtrack(i+1, n, m, cur) cur.pop() n, m = map(int, input().split())backtrack(1, n, m, [])문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 ..

알고리즘 분류백트래킹제출코드 1 (카타시안 곱 이용)import itertoolsn, m = map(int, input().split())numbers = [ n for n in range(1, n+1) ]for x in itertools.product(numbers, repeat=m): if len(x) == len(set(x)): print(*x)제출코드 2 (백트래킹 이용)def backtrack(n, m, cur): if len(cur) == m: print(*cur) return for i in range(1, n+1): if i not in cur: cur.append(i) backtrac..

알고리즘 분류다이나믹 프로그래밍제출 코드tc = int(input())list = [1, 2, 4]for i in range(3, 11): list.append(list[i-1]+list[i-2]+list[i-3])for _ in range(tc): n = int(input()) print(list[n-1])문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이..