SW Expert 3459 JAVA : 승자 예측하기

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

풀이 예상

앨리스,, 밥.... 누가 이기는건지 처음에 너무 헷갈렸다

1~20 정도까지 누가 이기는지 그려가면서 표를 작성했었는데 전혀 감이 안와서 다른 사람 풀이들을 봤다.

그랬더니 중간에 하나가 잘못 계산을 했어서 규칙이 안보였는데 규칙을 찾았다 ^0^;

1/4/4/16/16/64/64 .. 씩 승리를 번갈아 가면서 한다는 점

 

풀이방법 (접근 방법 & 시간복잡도)

 

시간복잡도 => 스터디 사람들 도와줘~~ 💟

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Solution {
    static int T;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
 
        for (int t = 1; t <= T; t++) {
            long num = Long.parseLong(br.readLine());
            sb.append("#").append(t).append(" ");
            check(num);
 
        }
        System.out.println(sb);
 
    }
    static void check(long num) {
        long count = 1;
        boolean checkTwo = false;
        long temp = 4;
        String currentPattern = "Bob";
 
        while (count < num) {
            if (currentPattern.equals("Alice")) {
                count += temp;
                currentPattern = "Bob";
                checkTwo = true;
            } else {
                count += temp;
                currentPattern = "Alice";
            }
 
            if(checkTwo) {
                temp *=4;
                checkTwo = false;
            }
        }
 
        sb.append(currentPattern).append("\n");
 
    }
}

 

 

 

다른풀이방법(참고 블로그) - https://4ngs.tistory.com/4

풀이 방법을 찾아보다가 신기했던 풀이 방법

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Solution {
    static int T;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        T = Integer.parseInt(br.readLine());
 
        for (int t = 1; t <= T; t++) {
            long num = Long.parseLong(br.readLine());
            sb.append("#").append(t).append(" ");
            check(num);
 
        }
        System.out.println(sb);
 
    }
    static void check(long num) {
        while(num > 10) {
            num = (num/2) + 1;
            num = (num/2) - 1;
        }
        if( num == 1 || (num >= 6 && num <= 9)){
            sb.append("Bob\n");
        }else {
            sb.append("Alice\n");
        }
    }
}

 

 

 

결과

 

위에가 내코드, 밑에가 참고한 코드