knight7024   5년 전

정말 이상한 방법(규칙성과 이진탐색을 이용)으로 풀기는 했습니다만(https://www.acmicpc.net/source...) 원래 풀이가 무엇인지 감을 종잡을 수가 없습니다.

제 풀이는 이렇습니다.

1에서 12까지 키가 큰다고 가정했을 때, 처음과 마지막은 1을 사용하여야 하므로 2에서 11까지 증가하고 감소하는 부분이 있을 것입니다. 여기서 규칙성을 이용합니다.

단순하게 상승만 한다고 가정하면, 키차이가 N일 때 총 X일이 걸립니다. 여기서, X * (X + 1) / 2 >= N입니다.

이제 반대로 생각해서, 감소하는 부분을 찾습니다.

b3506fe1-f9d2-4cf1-824f-e2e80741e357

M = 1, 2, 3 ... 이 숫자 중에서 위의 규칙에서 얻은 X와 일일히 비교하는 것입니다. 키는 하루에 1씩 높일 수 있으니 M과의 차가 절댓값이 1 이하면 그 부분부터가 감소의 시작이겠지요.

제 소스를 보시면 알겠지만 X를 찾는 반복문을 이진 탐색으로 돌려 0MS 안에 통과가 되긴 됐습니다. (일반 반복문으로는 2MS에 근접함.)

풀이를 횡설수설 작성해서 이해하실지 모르겠습니다만 ㅠㅠ... 제 이상한 풀이는 이렇습니다. 이거말고 다른 풀이를 알 수 있을까요? 문제 분류에서 수학은 O(1) 풀이인듯 하고 DP는 또 어떤 방법이 있나요? 구글에 검색해도 포스팅이 없는 문제는 처음입니다.

greedev   5년 전

https://www.acmicpc.net/source...

음...

다른 방법인가

k5nen   5년 전

1011번과 거의 같은 문제입니다.

https://www.acmicpc.net/proble...

키를 하루 11cm까지 늘렸다 줄이면 1 + 2 + .. + 10 + 11 + 10 + ... + 1 = 121을 늘릴 수 있고,

하루 12cm까지 늘렸다 줄이면  1 + 2 + .. + 11 + 12 + 11 + ... + 1 = 144를 늘릴 수 있습니다.

그러면 122~143 사이의 값은 어떻게 만들까요?  1...11...1 수열의 적당한 위치에 하루를 끼워넣으면 되겠네요.

이 관찰을 이용하면 O(1)로 풀 수 있습니다.


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