[백준 2024/01/25] 2164번 카드2

https://www.acmicpc.net/problem/2164

2164번: 카드2

 

1. 접근 방법

이번 문제는 deque로 접근하면 쉽게 풀릴 것 같았다.

추가적으로 뭔가 규칙이 있을 것 같았다.

 

deque로 우선 코드를 작성하고 백준에 넣어봤더니 통과 되었다.

규칙적인 부분도 한번 해보고 싶어서 쭉 적어보았더니 다음과 같은 결과가 나왔다. 

rough draft

 

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;
    }
}