백준 27961번 고양이는 많을수록 좋다 - C++Algorithm/BOJ PS2024. 11. 9. 12:29
Table of Contents
문제
마법소녀인 마도카는 너무나도 고양이를 좋아하는 나머지 마법을 이용하여 고양이 N 마리를 집에서 키우기로 결심했다!
마도카는 한 번의 행동에서 다음 가지 마법 중 하나를 선택하여 사용한다. 처음에는 마도카의 집에 고양이가 존재하지 않는다.
- 생성 마법: 고양이 마리를 마도카의 집에 생성한다.
- 복제 마법: 마도카의 집에 있는 고양이 일부 또는 전부를 대상으로 하여 복제한다. 즉, 만약 현재 마도카의 집에 고양이가 k 마리 존재한다면, 마리 이상 마리 이하의 고양이를 마도카의 집에 추가할 수 있다.
마도카는 위의 가지 마법을 적절히 사용하여, 최소의 행동 횟수로 마도카의 집에 정확히 N 마리의 고양이가 있도록 만들고 싶다. 계산을 어려워하는 마도카를 위해 최소의 행동 횟수를 계산해주자!
입력
첫 번째 줄에 키우기를 원하는 고양이의 수 이 정수로 주어진다.
출력
첫 번째 줄에 정확히 마리의 고양이를 마도카의 집에 들일 수 있는 최소의 행동 횟수를 출력한다.
문제 링크
https://www.acmicpc.net/problem/27961
풀이
전형적인 그리디 문제다.
이 문제는 문제에 나와있는대로 1에서부터 시작해서 고양이 수를 정확히 맞추려고 하면 안되는 문제다.
문제의 조건에는 복제 마법은 $k$마리가 존재할 때, $0$부터 $k$마리를 생성할 수 있는 마법이라고 나와있으니, 절반만 넘기면 나머지는 알아서 채울 수 있다.
그러면 절반까지 얼마나 최적으로 갈 수 있냐가 핵심인데, 복제마법을 사용할 때 $k$마리를 생성하면 된다.
즉, 계속 2배를 해주면 된다는 것이다.
아주 당연하게도 생성 마법은 처음에만 사용하고 그 뒤로는 사용할 일이 전혀 없다.
C++ 코드
#include <iostream>
using namespace std;
long long N, answer = 1;
void input() {
cin >> N;
}
void solve() {
long long cat = 1;
while (true) {
if (cat >= N) {
break;
}
cat = cat * 2;
++answer;
}
}
void output() {
if (N == 0) {
cout << 0 << endl;
} else {
cout << answer << endl;
}
}
int main() {
input();
solve();
output();
}
변수의 범위에 조심하자...
그리고 $N$이 0이 될 수 있다는 것에도 조심해야한다.
'Algorithm > BOJ PS' 카테고리의 다른 글
백준 13417번 카드 문자열 - C++ (0) | 2024.11.11 |
---|---|
백준 14916번 거스름돈 - C++ (0) | 2024.11.10 |
백준 7569번 토마토 - C++ (0) | 2024.11.08 |
백준 25195번 Yes or yes - C++ (0) | 2024.11.07 |
백준 9020번 골드바흐의 추측 - SWIFT (0) | 2024.11.07 |
@노근 :: NOGUEN 블로그