BOJ 2839: 설탕 배달 _ 22.11.19.

블로그를 이제 시작해서 문제 리뷰를 이제 쓴다.
일단 지금 군 복무 중인데 뭐라도 해야할 거 같아서 일단 알고리즘 공부겸 코딩테스트 준비 겸 시작하게 되었다.

지금은 solved.ac에서 DP문제를 시작으로 많이 푼 문제부터 차근차근 풀어나갈 생각이다.
아 그리고 지금은 젤 만만한 파이썬으로 푼다!

대망의 첫 문제..!!
바로
링크 이거 어케 쓰는거냐-그냥 이거 클릭하면 됨
이다!!!

실버4 문제인데 나름 기본적이면서 생각을 좀 해야되는 문제이다.
근데 이거 문제도 적어야되나?! 링크 걸었는데 괜찮겠지

암튼 시작하자면 설탕을 3kg 5kg 봉지로 나눠 담았을 때 봉지 가장 적게 쓰면 몇개 쓰냐?? 이 문제이다.

처음에는 전체 설탕 kg를 3, 5 모듈 연산해서 할려고 했는데,,, 저번 학기에 배운 알고리즘 수업에서 저렇게 하면 예외 사항이 발생할 수도 있다는 것이 기억나서 DP로 바름업(bottom up의 미국식 발음) 방식으로 풀어봤다.
->알고 보니 저렇게 풀어도 된다!! 알고리즘 수업을 제대로 안들어서 어렴풋이 생각나서 그런 것 같다..! 다시 복습해야겠다.

나의 기본적인 풀이는 dp배열을 만드는데 배열의 인덱스를 우리가 받은 전체 설탕 kg 수 이고, 그 인덱스마다의 값은 우리가 찾는 봉지의 최소 개수이다.

다시 말하면 dp[18] = 4 라고 함은,,, 설탕 18kg를 담을 수 있는 봉지 최소 개수가 4개라는 뜻이고, dp[11] = 3 라고 함은,,, 설탕 11kg를 담을 수 있는 봉지 최소 개수가 3개라는 뜻이다.
물론 이 말이 무슨 말인지 처음에는 당연히 모른다. 나는 진짜 몰랐다. 지금도 어떻게 이해했는 지 잘 모르겠다..(머쓱 ㅋ 코천일지동 풉킼 아 아직 이해 못한건가)

암튼 저 값을 찾으려면 그 전에 값을 알아야한다. 예를 들어 18kg를 다 채울 때 그 전에는 몇키kg를 채울 수 있었겠느냐? 이 말이 좀 어려운데 직관 적으로 우리는 3kg 5kg 봉지만 사용하니까 18kg에 도달하기 전 바로 직전!! kg수는 18-3 = 15kg 18-5 = 13kg 둘 중에 하나 일 것이다. 15kg에서 3kg짜리 하나 더 쓰면 18kg 되고, 13kg에서 5kg짜리 하나 더 쓰면 18kg가 되니까아아아!!!

즉 18kg에 도달하기 전까지의 무게의 개수가 최소면 18kg는 그 최소+1이니까 당연히 최소일 것이라 이말이다!! 그래서 1kg부터 18kg까지 최솟값만 쭉쭉 채워주면 결국 해답을 구할 수 있다!

⌨이제 코드를 보자

N = int(input())
dp = [-1]*5001
dp[3] = 1
dp[5] = 1
if N > 5:
	for i in range(6,N+1):
		if dp[i-3] != -1 and dp[i-5] != -1:
			dp[i] = min(dp[i-3]+1, dp[i-5]+1)
		elif dp[i-3] != -1 or dp[i-5] != -1:
			dp[i] = max(dp[i-3]+1, dp[i-5]+1)
		elif dp[i-3] == -1 and dp[i-5] == -1:
			dp[i] = -1
print(dp[N])

먼저 dp 배열을 생성한다. 원래는 N을 받아서 N+1만큼 동적으로 만들어줬는데 5000까지 밖에 없어서 그냥 바로 5001개 만들어줬다. 근데 여기서 왜 +1을 하느냐?? 이건 그냥 가독성때문에 인덱스 자체를 직관적으로 kg로 볼려고 인덱스 1부터 사용할려고 그런 것이다.
만약 구해야되는 값이 15kg면 0부터 시작해서 dp[14]를 찾는 거보다 1부터 시작해서 dp[15]를 찾는 게 더 쉽다! 아님 말공

그리고 dp에서 중요한 initial value 정해주기
dp[3] = 1, dp[5] = 1 -> 3kg로 1개 5kg로 1개 가능하니깡
(그리고 주머니로 못만드는 kg는 -1 출력해야해서 배열 자체를 -1로 초기화 해줬다)

이제 for문 돌자.
N이 6보다 작을 때 1,2,3,4,5 일 때는 한쪽 눈 가리고도 몇개인지 아니까 6부터 시작했다.
먼저 내가 찾고자하는 kg까지 돌린다. 자 돌면서 생각해보자 i일 때 i-3이나 i-5가
1)둘다 있을 때, 2)하나는 있고 하나는 없을 때, 3)둘다 없을 때, 이 셋 중에 한 경우인데

둘다 있으면, 둘 중에 min값
둘다 없으면, 그냥 못만드는거니까 -1
하나는 있고 하나는 없으면,
이건 무조건 -1 이랑 자연수 값 중에 하나기 때문에 둘 중에 max값 선택해주면 자연스럽게 있는 거에 +1 되서 들어간다.

아 저기 코드에서 두번째 조건문 안에 첫번째 조건문 들어가지 않냐라고 생각할 수 있는데 적다 보니까 elif라서 두번째 조건문에서는 첫번째 조건이 안들어간당

🚄 우리가 17kg를 담는다 가정하고 전체 흐름을 생각하면..

6kg 부터 시작해보자

6kg를 찾으려면 이전 단계 3kg, 1kg에서 찾아야된다
그럼 3kg는 dp[3] = 1, dp[1] = -1 이므로 2번째 조건문이네 dp[3] 낙찰
->dp[6] = dp[6-3] + 1 = 2가 된다

다음 7kg
뭐 찾으면 되겠습니까? 바로 4kg, 2kg!
근데 dp[4], dp[2] 둘다 -1 이면 3번째 조건문 dp[7] = -1

다음 8kg
말 안해도 알겠지 5kg, 3kg
dp[5] = 1, dp[3] = 1 이니까 1번째 조건문인데 둘다 값 똑같으니까 dp[8] = 2

쭉쭉쭉쭉 가다가

15kg일때
12kg, 10kg
dp[12] = 4, dp[10] = 2 -> 1번째 조건문 -> dp[15] = dp[15-5] + 1 = 3 이 된다.

요런 식으로 하면 내가 원하는 봉지 최소 개수를 찾을 수 있다!

Review

군대 입대하고 거의 처음으로 푼 dp문제라 못풀 줄 알았는데 다행히 기억이 살아나서 풀 수 있었다. 난이도가 뭔가 지금 내 시기에 딱 적당해서 좋았다!! 이걸 어떻게 끝맺어야될진 모르겠는데.. 이렇게 일상이 아닌 이런 it적인 블로그 쓰는 건 처음이라 좀 어불어물하면서 내가 하고 싶은 말 다 적고 이러는 거 같은데,,,, 이게 맞나? 이거는 점차 개선하면 될 것 같다.. 그리고 평소 개인정비 시간에는 이렇게 길게는 못쓸 거 같고,, 짱 서고 비일 때 폰 받기 전에 이런 식으로 하나씩 쓰면 좋을 것 같다.. 물론 한문제를 푼다는 가정하에.. 점이 왤캐 많아
아자아자화이팅 할 수 있다.

줄 그어놓은 거는 중요한 말 아니니까 안읽어도 됨유~

내가 만든 Cookie~

(쿠키 영상 뭐 그런거임)

N = int(input())
dp = [-1]*(N+1)
if N < 6:
	dp[3] = 1
	print(dp[N])
else:
	dp[3] = 1
	dp[5] = 1
	for i in range(6,N+1):
		if dp[i-3] != -1 and dp[i-5] != -1:
			dp[i] = min(dp[i-3]+1, dp[i-5]+1)
		elif dp[i-3] != -1 or dp[i-5] != -1:
			dp[i] = max(dp[i-3]+1, dp[i-5]+1)
		elif dp[i-3] == -1 and dp[i-5] == -1:
			dp[i] = -1
		
	print(dp[N])

처음에 틀린 코드인데 조건문을 저렇게 해놔서 N이 2일 때 배열이 2인덱스까지 밖에 안만들어져서 dp[3] 요게 런타임 에러 났당!! 조심하자!!