
코테99 16일차 문제는 백준 27961번 '고양이는 많을수록 좋다'다.


이번 문제는 그리디로 접근하는 것을 알고 있었지만, 내가 생각해낸 접근법이 맞나.. 하면서 문제를 풀었다.
문제 이해
- 마도카는 N마리의 고양이를 키우기 위해 2가지 마법을 사용한다.
- 고양이 한 마리를 추가한다.
- 일부 또는 전부의 고양이를 복제 (2배) 한다.
- N마리가 될 수 있는 마법의 최소 횟수를 출력한다.
알고리즘 진행 순서
- N을 입력받는다.
- cat이 N보다 작을 때까지 반복하면서
- 현재 cat * 2가 1보다 작거나 같으면 +1을 하고
- 아니라면, cat * 2를 cat에 넣는다
- count를 +1한다.
구현 코드
package Boj;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Boj27961 {
static long cat = 0;
static int count = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long N = Long.parseLong(br.readLine());
while (cat < N) {
if (cat * 2 <= 1) {
cat++;
} else {
cat = cat * 2;
}
count++;
}
System.out.println(count);
}
}
회고
- 그냥 우선 생각나는 대로 풀어보자.
'CS & Algorithm' 카테고리의 다른 글
[백준 / Java] 17053번: 맥주 축제 (그리디) (0) | 2025.02.13 |
---|---|
[백준 / Java] 11399번: ATM (그리디) (0) | 2025.02.12 |
[백준 / Java] 15686번: 치킨 배달 (백트래킹) (1) | 2025.02.08 |
[백준 / Java] 2615번: 오목 (브루트포스) (1) | 2025.02.06 |
[백준 / Java] 2529번: 부등호 (브루트포스 + 백트래킹) (0) | 2025.02.05 |