본문 바로가기

Algorithm(BOJ, Python)100

[백준_11052] 카드 구매하기 python 모든 경우의수를 비교해봐야 한다. n = int(input()) price = list(map(int, input().split())) price_list = [0] for p in price: price_list.append(p) dp = [ 0 for _ in range(n + 1) ] dp[1] = price_list[1] for i in range(2, n+1): for j in range(1, i + 1): if dp[i] < dp[i-j] + price_list[j]: dp[i] = dp[i-j] + price_list[j] print(dp[n]) 2022. 6. 25.
[백준_2502] 떡 먹는 호랑이 python 처음 이 문제를 접했을 때, dp인 것과 점화식은 너무 분명히 보였으나, 초기 값 설정을 어떻게 해야 할지 고민에 빠졌다. dp[d-1]부터 역추적을 해야 하나 했으나, 수가 그렇게 많지 않아 전수조사를 해도 나쁘지 않겠다는 아이디어가 떠올랐다. d, k = map(int, input().split()) dp = [ 0 for _ in range(31) ] for i in range(1, k): for j in range(i, k): dp[1] = i dp[2] = j for h in range(3, d + 1): dp[h] = dp[h-1] + dp[h-2] if dp[d] == k: print(dp[1]) print(dp[2]) quit() dp = [ 0 for _ in range(31) ] 2022. 6. 23.
[백준_17271] 리그 오브 레전설 (Small) python dp를 구현함에 있어서 무지성 세보기는 참 좋은 방법인 것 같다. 다만, 내가 구하는 칸이 어디서로부터 오는지 그 근본을 잘 확인해야 한다. dp = [ [0] * 101 for _ in range(10001) ] for i in range(1, 10001): dp[i][1] = (2 ** i) for i in range(1, 10001): for j in range(1, 101): if i == j: dp[i][j] = 2 elif i j: dp[i][j] = (dp[i-j][j] + dp[i-1][j]) n, m = map(int, input().split()) pri.. 2022. 6. 22.
[백준_2225] 합분해 python dp모르겠으면 진짜 3~4개는 세어보는게 답인 것 같다. 나도모르는 규칙이 나올지도? n, k = map(int, input().split()) dp = [ [0] * 201 for _ in range(201) ] for i in range(1, 201): dp[1][i] = 1 dp[i][1] = i for i in range(2, 201): for j in range(2, 201): dp[i][j] = dp[i-1][j] + dp[i][j-1] print(dp[k][n] % 1000000000) 2022. 6. 21.
[백준_10844] 쉬운 계단 수 python dp = [0 for _ in range(101)] for i in range(101): dp[i] = [0 for _ in range(10)] for i in range(1,10): dp[1][i] = 1 for i in range(2, 101): for j in range(10): if j == 0: dp[i][j] = dp[i-1][1] elif j == 9: dp[i][j] = dp[i-1][8] else: dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) n = int(input()) print(sum(dp[n]) % 1000000000) 2022. 6. 20.
[백준_15990] 1, 2, 3 더하기 5 python 규칙은 쉽게 찾았다. dp라는것을 아는데 시간이 걸렸을 뿐 import sys input = sys.stdin.readline dp = [0] * 100001 for i in range(100001): dp[i] = [0,0,0] dp[1] = [1,0,0] dp[2] = [0,1,0] dp[3] = [1,1,1] for i in range(4, 100001): dp[i][0] = (dp[i-1][1] + dp[i-1][2]) %1000000009 dp[i][1] = (dp[i-2][0] + dp[i-2][2]) %1000000009 dp[i][2] = (dp[i-3][0] + dp[i-3][1]) %1000000009 t = int(input()) for _ in range(t): n = int(inp.. 2022. 6. 18.
[백준_11727] 2×n 타일링 2 python 처음에 2*2 타일을 못보고 풀어서 애좀 먹었다. dp문제를 보고 바로 dp를 언제쯤 떠올릴 수 있을까. 난 정말 코테가 싫다. # 입력 받기 n = int(input()) # dp dp = [0] * (n+1) # 초기 설정 dp[0] = 1 dp[1] = 1 for i in range(2, n+1): dp[i] = (dp[i-1] + 2*dp[i-2]) % 10007 print(dp[-1]) 2022. 6. 16.
[백준_1074] Z python # 입력 받기 N, r, c = map(int, input().split()) # ans 초기 설정 ans = 0 # 4사분면으로 나눠서 생각 -> 계속 좁혀 갈 예정 while N != 0: N -= 1 # 1사분면에 해당할 경우 if r = (2 ** N): ans += (2 ** (2 * N)) # 그 사분면의 맨 왼쪽 위 꼭짓점을 더해줌 c -= (2 ** N) # 다음 좁혀진 4사분면으로 이동 # 3사분면에 해당할 경우 elif r >= (2 ** N) and c < (2 ** N): ans += (2 ** (2 * N)) * 2 # 그 .. 2022. 6. 15.
[백준_1309] 동물원 python n = int(input()) dp = [0] * (n+1) for i in range(n+1): dp[i] = [0,0,0] dp[1][0] = 1 # 처음에 하나도 선택하지 않은 경우 dp[1][1] = 1 # 처음에 왼쪽을 선택한 경우 dp[1][2] = 1 # 처음에 오른쪽을 선택한 경우 for i in range(2, n+1): dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 9901 # 이번에 선택하지 않는것은 전에 왼쪽을 선택했어도, 오른쪽을 선택했어도, 선택하지 않았어도 가능함 dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901 # 이번에 왼쪽을 선택하는것은 전에 선택하지 않았거나, 오른쪽을 선택했을 .. 2022. 6. 14.
[백준_10407] 2타워 python h = int(input()) if h == 1: print(2) # 1을 제외한 모든 2타워의 계산값은 else: print(1) # 1이다. 2022. 6. 13.

티스토리툴바