[백준/JAVA] 9655번: 돌 게임

🔺 문제

9655번: 돌 게임

 

 

🔺 코드

- 풀이1) 재귀를 활용한 풀이

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        String result = recursion(N, "SK");
        System.out.println(result);
    }
    
    static String recursion(int rock, String name) {
        if(name.equals("SK")) {
            if(rock - 3 >= 0) {
                rock -= 3;
                return recursion(rock, "CY");
            }
            else if(rock - 1 >= 0) {
                rock--;
                return recursion(rock, "CY");
            } else if(rock == 0) {
                return "CY";
            }
        }
        else if(name.equals("CY")) {
            if(rock - 3 >= 0) {
                rock -= 3;
                return recursion(rock, "SK");
            }
            else if(rock - 1 >= 0) {
                rock--;
                return recursion(rock, "SK");
            } else if(rock == 0) {
                return "SK";
            }
        }
        return "";
    }
}

 

 

- 풀이2) DP를 활용한 풀이

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static String[] rock = new String[1001];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine()); // 돌 개수
        
        // 초기 상태 설정
        if (N >= 1) {
            rock[1] = "SK";
        }
        if (N >= 2) {
            rock[2] = "CY";
        }
        
        dp();
        
        System.out.println(rock[N]);
    }
    
    static void dp() {
        for (int cnt = 3; cnt <= N; cnt++) {
            if (rock[cnt - 1].equals("SK") && (cnt + 3 == N || cnt + 1 == N)) {
                rock[cnt] = "CY";
            } else if (rock[cnt - 1].equals("CY") && (cnt + 3 == N || cnt + 1 == N)) {
                rock[cnt] = "SK";
            } else {
                if (rock[cnt - 1].equals("SK")) {
                    rock[cnt] = "CY";
                } else if (rock[cnt - 1].equals("CY")) {
                    rock[cnt] = "SK";
                }
            }
        }
    }
}

✅ 해결 아이디어
✔ DP
1) 테이블 정의하기
- rock[i] = name : DP 배열 rock의 i번째 값은 name

2) 점화식 세우기

3) 초기값 설정하기
- N의 크기가 1이라면, N[1] = "SK"
- N의 크기가 2라면, N[2] = "CY";

 

 

---

🔺 다른 풀이들

- 찢는 풀이 발견... 🙊🙊🙊

[BOJ] 백준 9655번 : 돌 게임 (JAVA)

 

- 나도 이렇게 풀었어야 했는데,,^^

[백준] 9655번 : 돌 게임 – JAVA [자바]

 

- 멋진 boolean 풀이..

[백준 9655번] 돌 게임 Java 풀이

---

💬 느낀 점

규칙만 발견하면 되는 것인데..

굉장히 비효율적으로 풀어버렸다 음하하...

담엔 더 단순하게 가보는걸로...

 

 

1회독	2회독	3회독	4회독	5회독
V	240309

 

 

(+ 240309 2회독 : 14376KB, 124s)

dp 안 쓰고 그냥 이렇게 풀어도 맞긴 했다....

문제의 의도는 이게 아닌 것 같지만...

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        if(N % 2 == 1)
            System.out.println("SK");
        else
            System.out.println("CY");
    }
}