1/28기록 - 백준 1094

브론즈는 어느정도 됐다고 생각해서 실버5를 도전해보고 있는데 오늘도 실버 5에서 한 문제를 도전해 보았다. 오늘은 백준 1094번 막대기 문제이다.

 

 

문제는 이러하다. 처음에 읽으면서 이게 뭔 소린가 하면서 3~4번을 다시 읽었던 것 같은데, 결국 예제 입력을 보면서 문제에서 주어진 방식을 하나씩 따라 가다 보니 완벽히 이해를 할 수 있었다. 예제 입력 1을 보면 23을 입력받았고, 64부터 계속 반복해서 나눈 막대기값은 32, 16, 8, 4, 2, 1 이다. 여기서 16, 4, 2, 1을 조합하면 23을 만들어 낼 수 있다. 그래서 조합한 막대기 개수는 4개. 예제 입력 2를 보면 32의 경우 64, 32 에서 바로 32 하나를 가지고 만들 수 있으므로 조합한 막대기 수는 1개가 된다.

 

알고리즘 생각

1. X를 입력받는다.

2. 문제를 풀어서 해석해 보면 X가 64보다 작은 경우를 시작으로 계속 절반씩 나누어서 0보다는 큰 숫자를 여러개 만들고 그것들을 조합하여 X와 같은 수를 만드는 개수를 파악하는 것이다.

3. 2번을 토대로 계속 절반씩 나누어야 하니까 while문을 택한다.

4. 조건에서 또 헷갈리게 적어놓았는데, 모든 막대를 풀로 붙여서 X를 만드는 것이지만, 프로그램 상에서는 count를 해주기 위해서 해당 값을 계속 빼주고 빼줄때마다 count변수를 올려주는 방식을 택할 수 있다.

5. 만약 X가 64가 나올 경우 count를 하나 올려주고 바로 break.

 

 

 

이렇게 해결할 수 있었다. 코드만 보면 이게 왜 실버 5지? 할 수 있는데, 문제 이해가 생각보다 어려웠다. 3~4번 읽어야 무슨 말인지 정확히 이해가 되었으니... ㅋㅋㅋㅋㅋ

 

 

1/28 기록 끝!!!!!!!!