미소를뿌리는감자의 코딩
[백준 2024/01/25] 2164번 카드2 본문
https://www.acmicpc.net/problem/2164
1. 접근 방법
이번 문제는 deque로 접근하면 쉽게 풀릴 것 같았다.
추가적으로 뭔가 규칙이 있을 것 같았다.
deque로 우선 코드를 작성하고 백준에 넣어봤더니 통과 되었다.
규칙적인 부분도 한번 해보고 싶어서 쭉 적어보았더니 다음과 같은 결과가 나왔다.
2의 n승 일 때마다 해당 카드의 개수가 마지막으로 남게 되는 카드의 수 였다.
만약 2의 제곱수가 아닌 카드의 마지막으로 남게 되는 수는 2의 배수였다.
즉,
8개 -> 8
9개 -> 2
10개 -> 4
11개 -> 6
12개 -> 8
13개 -> 10
14개 -> 12
15개 -> 14
16개 -> 16
이런식으로 규칙 있게 진행됨을 알 수 있었다.
n/Math.pow(2, i) 일 때,
Math.pow(2,i) - (Math.pow(2,i)-n)*2 가 남게 되는 카드의 수라고 유추했다.
식을 정리해보면, 2*n - Math.pow(2,i) 이다.
뭔가 더 잘 정리할 수 있을 것 같은데, 아쉽다.
+ 그래서, 여러 코드들을 참고해서 보았다.
카드 개수 로그를 씌운 값의 나머지를 버리고, 그 값을 2의 n승을 하게 되면,
즉,
(int)Math.pow(2, (int)(Math.log(num)/Math.log(2)))
다음과 같은 결과가 나온다.
8개 -> 8 => 4
9개 -> 2 => 8
10개 -> 4 => 8
11개 -> 6 => 8
12개 -> 8 => 8
13개 -> 10 => 8
14개 -> 12 => 8
15개 -> 14 => 8
16개 -> 16 => 16
여기서, 위 식으로 나온 값을 x라고 했을 때,
2*(n-x)가 남은 카드의 값이다.
만약, 2*(n-x)가 0이라면, n의 값 그대로를 출력해야 한다.
++++
이렇게 세 방법으로 문제를 풀어보았고,
메모리와 시간적 측면에서 더 낫다는 것을 확인할 수 있었다.
맨 위의 맞았습니다!! 는 로그 씌워서 계산한 값
두 번째 맞았습니다!! 는 내가 식을 생각해내서 계산한 값
마지막을 Deque를 사용해서 계산한 값이다.
예상 외로 첫 번째와 두 번째가 차이가 안나서 신기하고,
무조건 어려운 식이 정해는 아니구나 라는 생각도 들었다.
유동적으로 생각을 하도록 노력해야겠다.
탱탱한 뇌~
2. 코드
1) Deque를 적용한 코드
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.*;
public class b2164 {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
Deque<Integer> deque = new ArrayDeque<>();
int num1 = Integer.parseInt(reader.readLine());
for(int i=1; i<= num1; i++){
deque.addLast(i);
}
while(deque.size()!=1){
deque.removeFirst();
deque.addLast(deque.removeFirst());
}
System.out.println(deque.getFirst());
}
}
2) 규칙을 적용한 코드
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.*;
public class b2164_2 {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int num1 = Integer.parseInt(reader.readLine());
System.out.println(card(num1));
}
public static int card(int num){
for(int i = 0; i<= num; i++){
if(num == Math.pow(2, i)){
return num;
}
if((int)(num/Math.pow(2,i))==0){
return (int)(2*num - Math.pow(2,i));
}
}
return -1;
}
}
3) 로그 쓰는 식
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.BufferedReader;
public class b2164_2 {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int num1 = Integer.parseInt(reader.readLine());
System.out.println(card(num1));
}
public static int card(int num){
if(num==1) return 1;
int a = 2*(num - (int)Math.pow(2, (int)(Math.log(num)/Math.log(2))));
return (a ==0)?num: a;
}
}
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/01/27] 11286번 절댓값 힙 (0) | 2024.01.27 |
---|---|
[백준 2024/01/26] 1259번 팰린드롬수 (0) | 2024.01.27 |
[백준 2024/01/24] 1920번 수 찾기 (2) | 2024.01.24 |
[백준 2024/01/24] 1018번 체스판 다시 칠하기 (0) | 2024.01.24 |
[백준 2024/01/23] 12865번 평범한 배낭 (2) | 2024.01.23 |