반응형
문제
https://www.acmicpc.net/problem/1052
입력
첫째 줄에 N과 K가 주어진다. N은 10^7보다 작거나 같은 자연수이고, K는 1000보다 작거나 같은 자연수이다.
출력
첫째 줄에 상점에서 사야하는 물병의 최솟값을 출력한다. 만약 정답이 없을 경우에는 -1을 출력한다.
문제 풀이
문제 해석 및 계획
N을 2진수로 표현하여 1의 개수가 가져갈 물병의 개수가 될 것이라고 생각하여 N을 1씩 증가시키며 2진수로 표현하였을 때 1의 개수가 K와 같으면 될 것이라고 생각하였습니다.
오답 노트
부족한 물병은 물병을 합치지 않았다면 개수가 증가한다는 것을 생각하지 못하였습니다.
package main
import (
"bufio"
"fmt"
"os"
)
func main(){
reader := bufio.NewReader(os.Stdin)
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()
var N, K int
fmt.Fscan(reader, &N, &K)
for i:=N ; ; i++ {
check := 0
testNum := i
for testNum > 0 {
if testNum%2 == 1 {
check++
}
testNum /= 2
}
if check == K {
fmt.Fprint(writer, i-N)
break
}
}
}
정답
N을 2진수로 표현하였을 때 1의 개수가 들고갈 물병의 개수입니다. 큰 물병은 합치기 전 상태로 돌린다면 1의 개수가 K보다 작거나 같은 경우는 물병을 추가할 필요가 없었습니다. 이 점을 떠올리지 못하여 단순히 추가만 하려고 하여 입력 예시의 결과를 실패하며 막히게 되었습니다.
1의 개수가 K보다 큰 경우 물병을 줄여야하기에 물병을 하나씩 추가하며 확인하였습니다.
package main
import (
"bufio"
"fmt"
"os"
)
func main(){
reader := bufio.NewReader(os.Stdin)
writer := bufio.NewWriter(os.Stdout)
defer writer.Flush()
var N, K int
fmt.Fscan(reader, &N, &K)
for i:=N ; ; i++ {
check := 0
testNum := i
for testNum > 0 {
if testNum%2 == 1 {
check++
}
testNum /= 2
}
if check <= K {
fmt.Fprint(writer, i-N)
break
}
}
}
느낀 점
원리는 이해가 되는데 막상 구현을 하려니 예상하지 못한 변수들이 하나씩 발견되면서 점점 문제를 어렵게 생각하게 되었습니다. 풀고 나니 역시 문제의 난이도는 그렇게 높지 않았다고 느꼈지만 침착하지 못하여 문제를 어렵게 생각하였던 점에서 원리를 떠올렸을 때 잘못생각한 부분은 없는지 확인하는 침착함이 꼭 필요하다는 것을 배웠습니다.
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[Go] 백준 1124번 언더 프라임 (소수가 약점인 것 같습니다.) (0) | 2023.09.11 |
---|---|
[Go] 백준 1059번 킹 (반례를 못 찾았습니다.) (0) | 2023.09.10 |
[Go] 백준 24511번 queuestack (queue) (0) | 2023.09.08 |
[Go] 1152번 단어의 개수 (TrimSpace, Split) (0) | 2023.09.04 |
[Go] 백준 1005번 (위상 정렬, 깊이 우선 탐색) (0) | 2023.09.01 |