본문 바로가기
알고리즘 문제/CodeJam

[CodeJam][2018] Saving The Universe Again - Qualification Round

by 햄과함께 2019. 1. 22.
반응형

문제 : https://codejam.withgoogle.com/2018/challenges/00000000000000cb/dashboard




가장 뒤에 있는 CS를 바꾸는게 가장 큰 점수 하락을 만들 수 있다.

(damage, S 개수) 를 담는 map을 만든다.

문자열 P를 돌면서 문자열의 총 데미지를 구하고 map을 세팅한다.

만약 S 개수가 D 보다 크다면 아무리 많은 횟수로 바꾸더라도 D보다 작거나 같은 수를 만들 수 없다.

왜냐하면 S가 최소 1 데미지가 될 수 있기 때문이다.

최소 횟수를 구하려면 damage가 가장 큰 것부터 C와 바꿔나간다. 바꿔나가면서 총 데미지를 갱신한다. (총 데미지 = 총 데미지 - damage + damage/2)

C와 한 번 바꾼다면 그 S 문자는 데미지가 반으로 감소한다. (map[damage]은 1감소. map[damage/2]는 1증가.)

만약 map[damage]가 0이 된다면 비교하는 damage를 반으로 나눠서 다시 계속 탐색한다.

총 데미지가 D보다 작거나 같을때까지 이를 반복하면서 CS 교환횟수를 센다.


5pt 짜리 해답. 10pt 체점은 계속 Runtime error 뜬다.

어디가 문제일까 끄응..




소스코드 : https://gist.github.com/fpdjsns/29a8c22f51a04d7331d326cd68701aaa


반응형

태그

댓글0