[Java] 백준 9657 돌 게임 3

Lee GaEun·2024년 11월 22일

JAVA 알고리즘 백준

[Java] 알고리즘

목록 보기

22/93

9657 돌 게임 3 문제 링크

문제분석

돌 N개를 상근이와 창영이가 번갈아가며 가져감
돌은 한 번에 1개, 3개, 4개 가져갈 수 있음
마지막 돌을 가져가는 사람이 이김

제약 사항

게임은 항상 상근이가 먼저 시작
두 사람은 항상 최선의 선택을 함

입력 조건

첫째 줄 : 돌의 개수 N (1 ≤ N ≤ 1000)

출력 조건

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력

#1

N의 답을 구하기 위해서 하는 사전 계산을 arr에 저장
이렇게 하면 중복 계산을 피할 수 있음

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 1, 1, 2));

        findNext(arr, N, 5);
        System.out.println(arr.get(N-1) == 1 ? "SK" : "CY");

        sc.close(); // Scanner 닫기
    }

    static void findNext(ArrayList<Integer> arr, int N, int index) {
        if(N > index) {
            if(arr.get(index-1)==2 || arr.get(index-3)==2 || arr.get(index-4)==2) arr.add(1);
            else arr.add(2);
            findNext(arr, N, index+1);
        }
    }
}

#2

Arrays.asList(1, 2, 1, 1, 2) -> Arrays.asList(1, 2, 1, 1, 1) 수정
이게 초반 5가지 경우의 수만 미리 입력 해놓은 건데
5인 경우 계산을 잘못씀,, 5일 때 답은 "SK"임

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        ArrayList<Integer> arr = new ArrayList<>(Arrays.asList(1, 2, 1, 1, 1));

        findNext(arr, N, 5);
        System.out.println(arr.get(N-1) == 1 ? "SK" : "CY");

        sc.close(); // Scanner 닫기
    }

    static void findNext(ArrayList<Integer> arr, int N, int index) {
        if(N > index) {
            if(arr.get(index-1)==2 || arr.get(index-3)==2 || arr.get(index-4)==2) arr.add(1);
            else arr.add(2);
            findNext(arr, N, index+1);
        }
    }
}