프로그래머스 월간 챌린지 금과 은 운반하기 해설/코드 (파이썬)

코드만 보실 분은

GitHub - Rhyankwon/algorithms

 

문제설명 대충 하자면, i개만큼의 요소를 가진 g, s, w, t리스트가 있는데 g와 s는 i번째 요소에 할당된 a의 양과 b의 값이고 w는 한번에 i번째 요소의 g와 s리스트에서 한번에 뺄 수 있는 최대 값, t는 i째 요소에서 한번 값을 조정해줄 때마다 추가해야 하는 시간이다. 

처음에 별생각없이 if문이랑 이것저것 써서 풀었는데 1번이랑 24번만 맞아서 8.3점인가?ㅋㅋㅋㅋ가 나왔었다. 근데 나머지 문제들이 틀리거나 그런게 아니라 전부 시간초과가 나와서 이거 잘못풀었구나,,싶었다. 하긴 지금 와서 다시 조건을 보면 a와  b의 값이 10^9까지 가능하고, t[i]값도 10^5까지 가능하고, g[i], s[i]는 최악의 경우 대부분 0과 1로만 이뤄져있을 수도 있다. 그러면 최악의 경우 시간은 10^( 9 + 5)의 2배까지 걸릴 수가 있다. 

 

여튼 그래서 이건 혼자 못풀겠구나 싶어서 검색을 좀 해보니까 그냥 푸는 문제가 아니라 이분 탐색을 하라고 한다. 딱 감이 오긴 했는데 그러면 무슨 조건으로 이게 맞는지 확인을 하지? 라는 생각이 들었다. 근데 나는 혼자 똥꼬쇼하면서 월간 문제 2번 3번 풀고있었는데 알고보니 풀이가 이미 있더라...........;;ㅋㅋㅋㅋ 아니 뭐 공부목적이니까 상관없긴한데 그냥 어.. 풀이가이미있는줄은몰랏지

월간 코드 챌린지 시즌3 9월 해설

답이 나오는 조건이 있고 그걸 벡터적으로 풀이를 해놨는데 기울기가 -1이고 이런..부분들이 나는 조금 이해하기가 힘들었다. 그래서 그냥 설명해놓은걸 토대로 혼자 고민을 해봤는데, 결국 이렇게 생각하면 이해하기가 쉽다.

 

1. g 우선으로 옮기는 경우 옮길 수 있는 g와 s의 양을 Gmax, Smin라고 하고, s를 우선적으로 옮긴 경우를 Gmin, Smax라고 해보자.

2. 이 때 Gmax + Smin = Gmin + Smax인데, 그 이유는 어차피 각각을 '우선적'으로 옮겼을 뿐 g가 없으면 s를 옮기는 등 각 i요소에서는 매번 최대로 운반할 수 있는 만큼 옮겼기 때문에 총 운반한 값은 같게 된다.

3. 사실상 total값은 그대로 인채 G와 S의 값은 (Gmin~Gmax, Smin~Smax)의 범위 안의 값을 모두 갖게 된다.

가령 t일때 가능한 g와 s의 값은 Gmax,Smin일 수도 있지만 g,s = Gmax -n, Smin +n 혹은 g,s = Gmin +m, Smax -m 이런 식으로 g+s=total을 만족하는 상태 안에서 그리고 g는 Gmax를 넘지 않고 s는 Smax를 넘지 않는 선에서 g와 s값은 모두 나올 수 있다. 

4. 따라서 만약 우리한테 필요한 a, b 쌍이 시간 t일때 가능한 g, s쌍안에 있다면 그 t는 답이 되는 조건을 만족하고 그 g,s쌍 안에 있는지 확인하려면 a+b<=total을 만족하는지 그리고 a<=Gmax, b<=Smax인지를 확인하면 된다.

5. 시간 범위를 정한 뒤 이분탐색으로 가장 최소로 소요되는 시간t를 탐색한다.

 

이해를 하고 나서 보면 왜 프로그래머스 해설에서 벡터로 설명했는지 대충 감이 온다. 좌표에 그림처럼 그리면 대충 1사분면안에 기울기 -1인 선이 하나 생기고(g와 s합값이 일정해야 하므로) a,b가 그 삼각형((0,0), (Gmin, Smax), (Gmax, Smin))(윤곽선포함)안에 있으면 조건을 만족하게 되는거..다. 설명을 잘 한건지 모르겠지만 대충 그런 느낌이다.

논리적으로 생각했을 때 만약 w[i]값에 1이 없고 9, 5 이런식의 값만 있으면 g,s = Gmax -n, Smin +n 여기에서 값이 드문드문하게 나올 수 밖에 없지않나? 했는데 사실 w[i]값 안에서는 내가 원하는 만큼 값을 넣을 수 있기 때문에.. 바보같은 생각이다. ㅋㅋㅋㅋ 

 

어려운 문제이지만 좋은 문제였던 것같음!