Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 |
Tags
- 브루트포스
- 네트워크 계층
- 트리
- 99클럽
- 그래프 이론
- 프로그래머스
- Spring
- 코딩테스트준비
- 완전탐색
- Til
- 그래프
- 항해99
- Java
- 스프링
- BFS
- 백준
- 동적 프로그래밍
- 알고리즘
- DFS
- 정렬
- 그리디
- 우선순위큐
- 백트래킹
- 자바
- 스프링 핵심 원리 - 기본편
- 개발자취업
- DP
- lower bound
- BinarySearch
- 데이터베이스
Archives
- Today
- Total
AtraFelis's Develop Diary
[99클럽 코테스터디 16일차 TIL / 백준] 27961 - 고양이는 많을 수록 좋다 (그리디) 본문
99클럽 코테스터디 16일차 TIL
KeyWord : 그리디
문제
마법소녀인 마도카는 너무나도 고양이를 좋아하는 나머지 마법을 이용하여 고양이 N$N$마리를 집에서 키우기로 결심했다!
마도카는 한 번의 행동에서 다음 $2$가지 마법 중 하나를 선택하여 사용한다. 처음에는 마도카의 집에 고양이가 존재하지 않는다.
- 생성 마법: 고양이 $1$마리를 마도카의 집에 생성한다.
- 복제 마법: 마도카의 집에 있는 고양이 일부 또는 전부를 대상으로 하여 복제한다. 즉, 만약 현재 마도카의 집에 고양이가 $k$마리 존재한다면, $0$마리 이상 $k$마리 이하의 고양이를 마도카의 집에 추가할 수 있다.
마도카는 위의 $2$가지 마법을 적절히 사용하여, 최소의 행동 횟수로 마도카의 집에 정확히 $N$마리의 고양이가 있도록 만들고 싶다. 계산을 어려워하는 마도카를 위해 최소의 행동 횟수를 계산해주자!
입력
첫 번째 줄에 키우기를 원하는 고양이의 수 $N(0\leq N\leq 10^{12})$이 정수로 주어진다.
출력
첫 번째 줄에 정확히 $N$마리의 고양이를 마도카의 집에 들일 수 있는 최소의 행동 횟수를 출력한다.
풀이
매우 기초적인 그리디 문제였다.
로직은 아래와 같다.
- 생성 마법 $1$번 : 초기 고양이는 0마리이므로 복제마법이 불가능하다.
- 복제마법 $k-1$번 : 고양이 수를 계속 2배로 늘린다.
- 최초로 고양이 수가 N 이상이 되면 문제의 해를 찾게 된다.
여기서 2번 사항이 이 문제가 그리디인 이유이다.
일단 무조건 욕심내어 최댓값인 2배씩 고양이의 수를 증가시키다보면, 문제의 해를 구할 수 있다는 점에서 그렇다.
주의할 점은 2가지 정도 있었다.
- 입력 값인 N의 범위가 int 자료형의 범위를 초과할 수 있다.
- N이 0일 경우에는 예외적으로 0을 출력해주어야 한다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
long N = Long.parseLong(br.readLine());
long answer = 1L;
long cnt = 1L; // 생성마법 1번
while (cnt < N) {
answer++;
cnt *= 2;
}
System.out.println(N == 0 ? 0 : answer);
}
}
여담
처음에 문제 제대로 안 읽고 복제 마법은 무조건 2배로 늘리는 거구나 생각했다가 틀렸더랬다.
문제 좀 꼼꼼히 읽고 풀자! 괜히 시간 낭비하지 말고.
'Algorithm > 백준' 카테고리의 다른 글
[99클럽 코테스터디 18일차 TIL / 백준] 17503 - 맥주 축제 (그리디, 정렬, 우선순위큐) (0) | 2025.02.12 |
---|---|
[99클럽 코테스터디 17일차 TIL / 백준] 11399 - ATM (그리디, 정렬) (0) | 2025.02.11 |
[99클럽 코테 스터디 15일차 TIL / 백준] 15685 - 치킨 배달 (브루트포스, 백트래킹) (0) | 2025.02.07 |
[99클럽 코테 스터디 14일차 TIL / 백준] 2615 - 오목 (브루트포스) (0) | 2025.02.06 |
[99클럽 코테 스터디 13일차 TIL / 백준] 2529 - 부등호 (브루트포스, 백트래킹) (0) | 2025.02.05 |