[백준 1094 - 실버5] 막대기.cpp

https://www.acmicpc.net/problem/1094 

1094번: 막대기

 

문제를 보니 뭔가 규칙이 있을 것만 같았다.

더 생각해보니 2진법을 활용하면 풀릴 듯.

64를 계속 절반으로 나누어가며 내가 원하는 길이를 만든다.

64는 2진법으로 100 0000이다.

만약, 길이가 3인 막대기를 만들고 싶다면,

길이 2와 1인 막대기를 붙히면 된다.

-> 000 0011이라고 생각하면 되는 듯.

 

즉, 주어진 수를 2진법으로 표기하면

내가 붙혀야할 막대기의 정보를 알 수 있다는 것.

 

10진법을 2진법으로 바꾸기 위해선,

10진법으로 표기된 수를 2로 나누어가며,

나머지 값을 차곡차곡 쌓아주면 된다.

 

15를 예로 들어 보자.

15를 2로 나누면 몫이 7 그리고 1이 남는다.

그리고 몫이었던 7을 다시 나누면 3과 1이 남는다.

이를 반복하면,

15 = 7 * 2 + 1

7 = 3 * 2 + 1

3 = 1 * 2 + 1

1 = 0 * 2 + 1

이다.

여기서 나머지 값만 위에서부터 챙겨주면 2진법 표기가 된다.

2진법 1111 = 10진법 15

 

문제에서는 막대기 개수를 구하라고 했으므로,

2진법 표기로 바꾼 후, 1의 개수를 세아리는 것과 같았다.

따라서, N을 2로 나누어주며,

반복마다 나머지 값을 더해주었다.

 

(+) 함께 공부하는 친구는 문제에서 주어진대로 구현해주었다.

그래도 정답을 확인할 수 있었다.

---

이 문제는 약 한달 전 쯤 푼 문제였다.

지금보니 비트연산으로도 충분히 가능할 것 같은데...

기회가 되면 풀었던 문제도 다시 풀어봐야겠다.