sgc109   1년 전

처음에 이 문제를 풀려고할 때에는

100번 채널부터 N번 채널까지 +와 - 만으로 눌러야할 최소횟수와

고장나지않은 숫자버튼으로 가능한한 N번채널까지 가까이 간뒤 +와 -로 맞출때 눌러야할 최소 횟수

이 두 값중에 더 작은 값을 출력하도록 만들려고하다가 생각하면 할 수록 고려해야 할것들이 점점 많아진다는것을 느끼고 좀더 단순하게 가기위해


고장나지않은 숫자버튼으로 만들 수 있는 1~6 자리 조합을 모두 만든뒤 반복문을 돌려서 각각의 채널까지 숫자버튼을 눌러 간 후 N까지는 최소한의 + - 버튼을 눌렀을때의 총 버튼 누른 횟수를 계산하여 최소값을 구하고자 했습니다.(물론 모든 숫자버튼이 고장났을땐 + - 버튼이 최소한으로 눌린것을출력)

아무리 많아봐야 10^6 번 정도 반복되고, 10^6 개의 인덱스가 필요할거라고 생각했기때문에

충분히 문제를 해결할 수 있을거라고 생각했기때문입니다. 하지만 돌려본결과... 500000 0 을 입력값으로 넣자 5~6 초 정도가 걸리는 듯 싶었고

뭔가 최적화를 하거나 좀 번거롭더라도 기존의 생각한 방식대로 풀어야 겠다는 생각이 들었습니다. 우선 최적화를 해서 풀고싶은데

어떤 방법이 있을까요?


+p.s. 그리고 처음에 comb 배열대신 vector<string> comb 를 사용했었는데 너무느려서 배열로 바꾸니 1~2초정도 빨라진 느낌이 들었는데

이론상으로 확실히 더 빨라지는게 맞나요?

@hongjun7

appa   1년 전

나중에 풀어보고 답글 남기겠습니다...

sgc109   1년 전

@hongjun7 네알겠습니다^^

댓글을 작성하려면 로그인해야 합니다.