소민's Blog

연속합 첫 풀이오류 원인if i == 0: dp[i] = max(0, numbers[i])-5 -2 -3 일때 max(dp)에서 dp[0]=0 이 채택되면 없는 값이 선택 되는 것n = int(input())numbers = list(map(int, input().split()))dp = numbers[:]for i in range(n): if i == 0: dp[i] = max(0, numbers[i]) continue dp[i] = max(numbers[i], dp[i-1]+numbers[i])print(max(dp)) 내 풀이해당 위치값부터 시작하거나이전값에서 해당위치값을 더하거나2가지 경우 중 선택n = int(input())numbers = list(ma..

RGB거리 각 col, row가 어떤 값인지 주의해서 넣을 것n = int(input())graph = [list(map(int, input().split())) for _ in range(n)]dp = [[float('inf') for _ in range(3)] for _ in range(n)]for i in range(n): for j in range(3): if i == 0: dp[i][j] = graph[i][j] continue for k in range(3): if j == k: continue dp[i][j] = min(dp[i][j], dp[i-1][k]+..

설탕 배달 초기화할때 n이 초기화하는 값보다 작은 경우를 고려해줘야함n=int(input())dp=[float('inf') for _ in range(n+1)]if n>=3: dp[3]=1if n>=5: dp[5]=1for i in range(5, n+1): dp[i]=min(dp[i],min(dp[i-3],dp[i-5])+1)if dp[n]==float('inf'): print(-1)else: print(dp[n])

2839. 설탕 배달 내 풀이dp[i] = i kg을 만들 때 필요한 최소 봉지 수.기본값: dp[3] = 1, dp[5] = 1점화식 구현 방식i-3, i-5 둘 다 불가능(=0) → dp[i]도 불가능(=0)두 값이 다 가능하면 → dp[i] = min(dp[i-3], dp[i-5]) + 1한쪽만 가능하면 → 그쪽 값 + 1즉, 불가능한 값(0)은 min 비교에 넣으면 안 됨.n = int(input())dp = [0 for _ in range(max(6, n+1))]dp[3] = 1dp[5] = 1for i in range(6, n+1): if dp[i-3] == 0 and dp[i-5] == 0: continue if dp[i-3] != 0 and dp[i-5] != 0:..

거스름돈 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 내 풀이중복을 막으려면, 동전 단위별로 바깥 루프를 돌려야 함.예를 들어 1,2,5 동전으로 5원을 만드는 경우의 수를 세려면,1원을 기준으로 다 만들고 → 2원을 추가해서 만들고 → 5원을 추가하는 순서로 진행해야 중복이 제거됨 누적 DP: 앞의 수들을 만들 수 있는 방법의 수를 누적한 값def solution(n, money): INF=1000000007 dp=[0 for _ in range(n+1)] dp[0]=1 for m in money: # 중복 방지하려면 한 화폐로 만들 수 있는 수 한 번씩만 체크 ..

11066. 파일 합치기 풀이 참고: https://supersfel.tistory.com/entry/11066다른 사람 풀이한 번에 두 개의 파일만 합칠 수 있고, 파일의 순서는 유지되어야함dp[i][j]: i번째 파일부터 j번째 파일까지 합치는 최소 비용prefix_sum[i]: 1번부터 i번까지의 누적 합 (구간합 빠르게 구하기 위함)[40,30,30] 일때 [40,30]+[30] [40]+[30,30] 둘 중에 뭐든 간에 [a,b]+c 의 비용: (a+b) + (a+b)+c 이기 때문에 무조건 a+b+c를 더하게 되어있기 때문구간 길이를 2,3,... 늘려가며 확인최종 정답은 dp[1][k] (전체 파일 합치는 최소 비용)t = int(input())for _ in range(t): k = ..

연속 펄스 부분 수열의 합 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이나는 최장 연속 부분 수열처럼 투포인터로 하되, 합친 값이 0 이상인 경우까지 2차원으로 구해두고 확인하려함하지만 이문제는 투포인터 문제가 아님투포인터의 전제투포인터(two pointers)는 보통 다음 조건에서 사용됨1. 구간의 조건이 "단조성(monotonic)"을 가질 때 예: 구간 합이 K 이상이면 오른쪽 포인터를 옮기고, 작으면 왼쪽 포인터를 옮기는 방식.2. 특정한 조건을 만족하는 구간의 최소 길이, 개수 등을 찾을 때 3. 정렬된 배열, 슬라이딩 윈도우 등에서 성능 최적화를 위해 많이 사용 📍 이 문제는 왜 투포..

1446. 지름길 내 풀이O(D + N)이라 완탐했음DFS + DPdp[i]: 0에서 i까지 도달하는 데 필요한 최소 거리현재 위치에서 갈 수 있는 지름길 or 직진을 따라가며 최소 거리 갱신from collections import defaultdictn,d=(map(int,input().split()))road=defaultdict(list)for _ in range(n): s,e,k=map(int,input().split()) road[s].append((e,k))dp=[i for i in range(d+1)]def dfs(end,total): if end>d: return if dp[end] 다른 풀이- DP + 선형 탐색 (Bottom-Up 방식) DFS 호출..

가장 긴 팰린드롬 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 내 풀이n=2500이라 O(N^2)도 가능두 포인터(i, j) 돌리면서 양 끝을 비교해당 부분 문자열 전체를 뒤집어서 같은지 확인s[i:j+1] == s[i:j+1][::-1]def solution(s): n = len(s) answer = 0 for i in range(n): for j in range(n-1, i-1, -1): if s[i] == s[j]: if s[i:j+1] == s[i:j+1][::-1]: answer = ..

1699. 제곱수의 합 내 풀이i가 제곱수가 아니라면, 모든 가능한 제곱수 j²를 확인i를 j²와 i-j²로 나눈다고 생각하고,dp[i] = min(dp[i], dp[j²] + dp[i-j²])로 최소값을 갱신n = int(input())dp = [float('inf') for _ in range(n+1)]dp[0] = 0dp[1] = 1for i in range(2, n+1): if i**0.5 == int(i**0.5): dp[i] = 1 continue for j in range(1, int(i**0.5)+1): dp[i] = min(dp[i], dp[j**2]+dp[i-(j**2)])print(dp[n])