[JAVA] 백준 2164번: 카드2

 

---

문제

• N이 주어지면 1부터 N까지의 카드를 순서대로 보유하고, 아래의 순서대로 연산을 반복한다.
  • 가장 첫번째 카드를 버린다.
  • 그 다음 첫번째 카드를 맨 뒤로 옮긴다.
  • 이 과정을 카드가 한 장 남을 때까지 반복한다.
• 이렇게 연산을 수행한 후 제일 마지막에 남게 되는 카드를 출력하는 문제.

 

아이디어

• (첫 풀이) 맨 앞의 요소를 맨 뒤로 옮기는데 가장 간단하게 사용 할 수 있는 자료구조는 큐이다.
• 큐를 이용해 해당 연산을 직접 구현한다.
• (두번째 풀이) 직접 연산을 수행하며 답을 나열하면 다음과 같다.
  • 1,
  • 2,
  • 2, 4,
  • 2, 4, 6, 8,
  • 2, 4, 6, 8, 10, 12, 14, 16,
  • ...
• 규칙성을 찾으면 숫자가 2^i 개씩 증가하며, 각 수열이 생기는 것을 알 수 있다. 
• 그리고 정답은 해당 수열에서의 수 위치 x 2
• 이 규칙을 코드로 구현한다.

 

풀이 1

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Deque<Integer> queue = new ArrayDeque<>();

        int N = Integer.parseInt(br.readLine());
        
        // 큐에 1부터 N까지 저장
        for(int i=1; i<N+1; i++) {
            queue.addLast(i);
        }

        int answer = 0;
        
        // 큐에 카드가 남아있지 않을 때까지 반복
        while(true) {
            answer = queue.removeFirst();
            if(queue.isEmpty()){
                break;
            }
            queue.addLast(queue.removeFirst());
        }
        System.out.println(answer);

    }
}

 

풀이 2

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int num = 1;
        
        // 1일때는 규칙에서 배제
        if(N == 1) {
            System.out.println(1);
            return;
        }
        
        // 2의 거듭제곱 중 N에 가장 근사한 값을 구해 몇번째 수열에 속하는지 체크
        while(num < N) {
            num *= 2;
        }
        num /= 2;
        
        // 수열 중 몇번째수인지 구하고(N-num)
        // 2를 곱해 해답을 도출
        System.out.println((N-num)*2);


        // 1,
        // 2,
        // 2,4,
        // 2,4,6,8,
        // 2,4,6,8,10,12,14,16,
        // 2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32
    }
}

 

채점 결과

풀이 1(아래), 풀이 2(위)

기타

• 역시 순수 구현 or 완탐으로 문제를 풀고 시간을 줄이는 쪽이 최고다.

 

문제 링크

• 2164번: 카드2 (acmicpc.net)