백준/ Silver 1 문제 , 백준 파이썬 9465 , 스티커

백준/ Silver 1 문제 , 백준 파이썬 9465 , 스티커

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
한시간좀넘게 걸렸다. 처음에는 구간을 나눠서 최적의 경로를 비교해가며 찾으려고했으나 코드가 너무 길어지고 칸이 너무 길어지면 시간초과가 날게 뻔해서 생각을 바꿨다.

 

<문제 출처>

 

https://www.acmicpc.net/problem/9465

9465번: 스티커

------------------------------------------------------------------------------------------------------------------------------

 

 

 

합을 누적해가며 문제를 해결해 나가자.

 

이 과정은 n이 1 이상일 때만 적용되고

 

당연히 n=1 이라면 그냥 그대로 제일 큰 값만 출력 주면 된다.

 

우선 n>2 이상인 상황에서 for 문을 돌려주고 

 

1열에 해당하는 값은 우선 계산해 둔다. 경우의 수가 한가지 씩 밖에 없기때문에

 

 

50	40(30+10)	100	20	40
30	100(50+50)	70	10	60

 

대각선으로 더해주면 이렇게 되겠다.

 

 

이 코드를 실행한 것이다.

 

 

이후부터는 경우의 수들이 좀 생겨서 비교를 해가며 가장 큰 값을 찾아야한다.

 

 

100에 더 할 수있는 경우의 수들은

 

 

1)

50		100
	100(50+50)

 

2)

		100
30

 

이렇게 두가지로 나뉜다.

 

 

이 값들중에 큰값을 더해줘야하므로

 

 

 

이렇게 max를 통해 두 값을 비교해서 더해준다.

 

그렇다면 100 밑에값 70도 비슷한 방식이겠다.

 

1)

	40(30+10)
30		70

 

2)

50
		70

 

 

이렇게 똑같이 두경우로 나뉠 것이고,

 

 

같이 계산해주면 된다.

 

 

 

이런식으로 끝까지 계산하다보면 up과 down 끝값에는 최종 값들이 저장되어있고

 

이 둘 중 큰값을 출력하면 출력해야할 답이 된다.

 

 

 

 

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답