문제 링크 : 백준 2885번
[문제 접근]
k보다 큰 2의 배수 중 가장 작은 수를 찾고 2로 나누면서 최소 횟수를 구하면 시간초과가 발생한다.
2의 배수가 반복되는 문제라 규칙이 있어서 그리디하게 풀면 될 것 같았다.
먼저 1,000,000을 넘는 2의 배수 중에서 가장 작은 수까지 배열을 생성해주고 쪼갤 수 있는 정사각형 갯수를 미리 넣어준다.
ex) 8은 4,2,1로 나눌 수 있으므로 arr[8] = 3
k보다 큰 수 중에 가장 작은 2의 배수를 찾아서 첫 번째 출력을 구한다.(arr[temp]가 0이 아니면 2의 배수이므로 0이 아닐 때까지 1을 더하면서 찾는다.)
두 번째 출력은 규칙을 이용해서 찾았다.
- a가 홀수라고 할 때 a의 쪼개야하는 최소 횟수는 a의 2의 배수에도 동일하게 적용된다.
- 홀수는 1을 무조건 사용해야하므로 1까지 전부 쪼개야한다.
ex) 3의 쪼개야하는 최소 횟수는 정사각형 4개짜리 초콜릿을 2,1로 쪼개야하므로 2이다. 따라서 6,12,24,46....도 쪼개야하는 최소 횟수는 2이다.
결론적으로 k가 홀수가 될 때까지 2로 나누고 그 값보다 큰 2의 배수 중 가장 작은 수를 찾아서 1까지 쪼개는 횟수를 구하면 된다.(그 횟수는 처음 arr배열에 미리 넣어두었다.)
ex) k가 28이라고 할 때 28->14->7, 7보다 큰 2의 배수 중 가장 작은 수는 8이므로 arr[8]=3 이 정답이다.
실제로 28은 32를 3번 쪼개서 16+8+4로 만들 수 있다.
⭐️ 풀고나서 다른 사람은 어떻게 풀었는지 궁금해서 참고해봤는데 비트 연산으로 더 쉽게 풀 수 있는 것 같다.
[소스 코드]
package main
import (
"bufio"
"fmt"
"os"
)
var (
r = bufio.NewReader(os.Stdin)
w = bufio.NewWriter(os.Stdout)
k int
arr [1050000]int
)
func main() {
defer w.Flush()
fmt.Fscan(r, &k)
cnt := 0
for i := 1; i <= 1050000; i *= 2 {
arr[i] = cnt
cnt += 1
}
temp := k
for arr[temp] == 0 {
temp++
}
size := temp
for k%2 == 0 {
k /= 2
}
for arr[k] == 0 {
k++
}
num := arr[k]
fmt.Fprintln(w, size, num)
}