목록DP (9)
cmod.ify
처음에 2차원 리스트로 만들었더니 메모리 초과 ㅠㅠ어쩐지 너무 쉽더라import sysimport heapqinput = sys.stdin.readlinen = int(input())gra = []gra.append([0 for _ in range(n + 2)])for i in range(1, n + 1): li = list(map(int, input().strip().split())) gra.append([0] + li + [0])xdp = [[0] * (n + 2) for _ in range(n + 1)]ndp = [[sys.maxsize] * (n + 2) for _ in range(n + 1)]ndp[0] = [0 for _ in range(n + 2)]for i in range(1, ..
입력 받는 리스트를 2차원으로 해도 되지만 직관적으로 1차원으로 하는 것을 선호한다 import sysinput = sys.stdin.readlinen = int(input())cost = [[0] * 3 for _ in range(n + 1)]red = [0]green = [0]blue = [0]for _ in range(n): r, g, b = map(int, input().strip().split()) red.append(r) green.append(g) blue.append(b)# 26 40 83# 40+49(89) 26+60(86) 26+57(83)# 13+83 89+84 99+86for i in range(1, n + 1): cost[i][0] = red[i] + m..
실패 코드그리디 구현import sysimport mathinput = sys.stdin.readlinen = int(input())cnt = 0while (n > 2): n = math.sqrt(n) print(n) cnt += 1print(cnt) 힌트를 받아 dp라는 것을 알았다그렇지만 점화식 세우는게 감이 안잡혀서 그냥 정답을 보고 이해하기로 했다import sysinput = sys.stdin.readlinen = int(input())d = [5] * (n+1)d[1] = 1for i in range(2,n+1): min_v = 5 j=1 while j*j i: if j*j == i: min_v = 1 bre..
11726 번 문제에서 2개만 바꾸면 된다1) 초깃값 fibo[2] = 32) 점화식 fibo[i-2]*2 점화식을 바꾼 이유는 ㅣ자 바가 하나로 합쳐진게 생겼다고 해서 ㅣ자 바 모양을 가진 fibo[i-2]를 두배했다. import sysinput = sys.stdin.readlinen = int(input())fibo = [0] * 1002fibo[0]=0fibo[1] = 1fibo[2] = 3for i in range(3,1002): fibo[i] = (fibo[i-1] + fibo[i-2]*2) %10007print(fibo[n])
괄호 안 쳤다가 틀렸었다 import sysinput = sys.stdin.readlinen = int(input())fibo = [0] * 1002fibo[0]=0fibo[1] = 1fibo[2] = 2for i in range(3,1002): fibo[i] = (fibo[i-1] + fibo[i-2]) %10007print(fibo[n])
1일 때 1,2일 때 2,3일 때 4,4일 때 7, .... i 번째 데이터는 i-1 + i-2 + i-3 의 값을 더하면 된다import sysinput = sys.stdin.readlinet = int(input())d = [0 for _ in range(12)]d[1] = 1d[2] = 2d[3] = 4for i in range(4, 12): cnt = d[i-1] + d[i-2] + d[i-3] d[i] = cntfor _ in range(t): n =int(input()) print(d[n])
처음에 점화식 쉽게 생각해서d[i-1] + s[i] 전칸까지의 합이랑 d[i-2] + s[i] 전전칸 까지의 합 중에 최댓값 구하면 되는게 아닌가 생각했는데그러면 무조건 모든 칸을 밟게 됨 규칙에선 3번 연속 밟으면 안 된다고 했음d[i-2]+stair[i] 한칸을 띄운 버전이랑 d[i-3] 두칸 전까지의 합에 한칸을 띄우고 stair[i-1] 이전칸의 합과 stair[i]현재까지의 합을 더해야 한다import sysinput = sys.stdin.readlinestair = [0] * 301n = int(input())for i in range(1, n+1): t = int(input()) stair[i] = td = [0] * 301d[1] = stair[1]d[2] = stair[1] +..
일단 처음에 재귀라고 생각을 했는데 실행시간이 짧아서 DP라고 생각은 들었는데 어떻게 해결해나갈지 감이 잘 안왔다.DP부분이 약해서 그냥 제미나이한테 도움을 받았다. (그런데 틀림) 틀린 코드import sysinput = sys.stdin.readlinen = int(input())d = [0] * (n+1)for i in range(2, n+1): d[i] = d[i-1] + 1 if i%2 == 0: d[i] = min(d[i], d[i//2] + 1) elif i%3 == 0: d[i] = min(d[i], d[i//3] + 1)print(d[n]) DP 초기 부분이 틀리지 않았을까 생각했다. 가변적으로 설정하니까 d[2]=1 값을 지정이 불가능해서 값을..
처음엔 피보나치 함수 DP쓰는 기본 방식에 전역변수로 cnt 의 개수를 세는 방법으로 풀었다근데 그럴 경우엔 dp를 쓰게 되니 접근하지 않는 0과 1의 개수를 놓치게 된다0과 1을 세는 dp로 채워 나가면서 풀어야 하는 문제다import sysinput = sys.stdin.readlinezero_count = [0] * 41one_count = [0] * 41zero_count[0]= 1one_count[1] = 1for i in range(2,41): zero_count[i] = zero_count[i-1] + zero_count[i-2] one_count[i] = one_count[i-1] + one_count[i-2]t= int(input())for _ in range(t): nu..