새해 알고리즘 스터디(1.1~7)
6일차
백준 문제 :
2225, 2011, 11052, 9465
{복습 1일차 1/9} 막연히 2-4시간씩 붙잡고 있던 풀이와 해설이 이해된다. 이제 몇분이면 이해할 수 있다!
DP 빡공 +5👩💻
DP 공부를 시작하는 마음가짐 🐳
◻️ 내 것이 될 때까지 물어보고 공부하고 정리하자
◻️ 파이써닉한 코드를 많이 보고 연구하자
◻️ 조급해 말고 나만 꽉 채우자
A) 2225번
1차 시도(성공):
# 0 ~ N까지의 정수 K개를 더해서 그 합이 K가 되어야 함
n, k = map(int, input().split())
dp = [[0] * (n + 1) for _ in range(k+1)]
dp[0][0] = 1
for i in range(1, k+1):
for j in range(n+1):
for m in range(j+1):
dp[i][j] += dp[i-1][j-m]
dp[i][j] %= 1000000000
print(dp[k][n])풀이:
- n = 2, k = 3
- i = k자리+1까지 순회 (1,2,3)
- j = n자리+1까지 순회 (0,1,2)
- m = (0, 1, 2)
dp[i][j] += dp[i-1][j-m] dp[3][2] = dp[3][2] + dp[2][2]->6 = 3 + 3
문제풀이 체크리스트
◻️ 시간 제한 지났음에도 문제 터치 못함
◼️ 시간 제한 후 코드 완성
◻️ 코드 미완성
◻️ 코드 완성 - 에러
◻️ 코드 완성 - 정답
B) 2011번
소스코드:
a = list(map(int, list(input())))
l = len(a)
# dp[i] : i번째 수 단계에서 암호 코드의 개수
dp = [0] * (l+1)
if a[0] == 0: # 암호 만들 수 없는 경우
print(0)
else :
a = [0] + a # 인덱싱을 위해 추가한 0
dp[0] = 1
dp[1] = 1 # 첫번째 수로 이뤄진 암호코드는 1개이다.
for i in range(2, l+1):
cur = a[i] # 한 자리
cur2 = a[i-1] * 10 + a[i] # 두 자리
if cur >= 1 and cur <= 9:
dp[i] += dp[i-1]
if cur2 >= 10 and cur2 <= 26:
dp[i] += dp[i-2]
dp[i] %= 1000000
print(dp[l])출처 - itsunny333
풀이:
- 숫자가 0이 아니면 한가지의 방법이 생긴다
--> d[i] = d[i] + d[i-1] - 이전 숫자와 합쳤을 때 26이하면 한가지의 방법이 추가로 생긴다
--> 현재 숫자의 두번째 전 숫자의 방법이 추가된다
--> d[i] = d[i] + d[i-2]
출처 - dontdiethere
문제풀이 체크리스트
◼️ 시간 제한 지났음에도 문제 터치 못함
◻️ 시간 제한 후 코드 완성
◻️ 코드 미완성
◻️ 코드 완성 - 에러
◻️ 코드 완성 - 정답
C) 11052번
규칙:
--> 카드 N개를 구매할 때의 최대 비용을 구해야하는 문제다.
1. 민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 레벨이 높은 카드가 많이 들어있다고 생각함
2. 따라서 민규는 돈을 최대비용을 지불해서 카드 N개 구매하고 싶음
3. 카드가 I개 포함된 카드의 가격은 P
ex) 민규가 카드 4개 갖고 싶어함
1. P1 = 1, P2 = 5, P3 = 6, P4 = 7 같은 경우 P2개 x 2 = 10만원으로 최댓값
--> P4 < P2 2 = 10
2. P1 = 5, P2 = 2, P3 = 8, P4 = 10 는 카드가 1개 들어있는 카드팩 x 4개 = 20만원이 최댓값
--> P4 < P1 4 = 20
3. P1 = 3, P2 = 5, P3 = 15, P4 = 16은 3개 들어있는 카드팩 + 1개 들어있는 카드팩 = 18원이 최댓값
--> P6 < P3 + P1 = 18
이와 같은 사항을 고려하며 각 요소합의 최댓값을 비교해야 한다:
(출처 - suri78)
1개를 살 때:
0 + 1
2개를 살 때:
0 + 2
1 + 1
3개를 살 때:
0 + 3
1 + 2
4개를 살 때:
0 + 4
1 + 3
2 + 2
점화식 : dp[i] = dp[i] vs (dp[i-j] + arr[j]) --> max() 함수로 둘 중 최댓값을 구하기
소스코드:
N = int(sys.stdin.readline())
price = [0]
price += list(map(int, sys.stdin.readline().split()))
for idx in range(1, N+1):
tmp = []
for t in range(idx//2 + 1):
tmp.append(price[t] + price[idx-t])
price[idx] = max(tmp)
sys.stdout.write(str(price[N]))출처 - suri78
풀이와 점화식을 보면 참 간단한 문제인데.. 복잡하게 접근했던 것 같다.
문제풀이 체크리스트
◼️ 시간 제한 지났음에도 문제 터치 못함
◻️ 시간 제한 후 코드 완성
◻️ 코드 미완성
◻️ 코드 완성 - 에러
◻️ 코드 완성 - 정답
D) 9465번
규칙:
- 점수의 합이 최대가 되도록 스티커를 떼어내야 함
- 서로 변을 공유하지 않는 스티커 집합을 구해야 함
소스코드:
def sticker(n):
point = []
for _ in range(2):
l = list(map(int, input().split()))
point.append(l)
point[0].insert(0, 0)
point[1].insert(0,0)
for i in range(2, n+1):
point[0][i] = max(point[1][i-1], point[1][i-2]+point[0][i])
point[1][i] = max(point[0][i-1], point[0][i-2]+point[1][i])
a1 = max(point[0])
a2 = max(point[1])
return max(a1, a2)
t = int(input())
for _ in range(t):
print(sticker(int(input())))출처 - cowimming
점화식 :
point[0].insert(0, 0)
point[1].insert(0, 0)
point[0][i] = max(point[1][i-1], point[1][i-2]+point[0][i])
point[1][i] = max(point[0][i-1], point[0][i-2]+point[1][i])이 문제 또한 매우 복잡하게 접근했다... 쉽게 생각했으면 점화식이라도 구했을텐데 아쉽다. 그래도 해당 풀이는 완벽히 숙지했다.
문제풀이 체크리스트
◼️ 시간 제한 지났음에도 문제 터치 못함
◻️ 시간 제한 후 코드 완성
◻️ 코드 미완성
◻️ 코드 완성 - 에러
◻️ 코드 완성 - 정답
7일차
7일차는 스티디 팀원들과 DFS, BFS를 맛보기로 했다. DP 문제도 혼자 연구해 봐야겠다.
Reference
https://www.acmicpc.net/
https://dontdiethere.tistory.com/85
https://it-sunny-333.tistory.com/78
https://suri78.tistory.com/107
https://cowimming.tistory.com/m/103
https://sungmin-joo.tistory.com/42
