[백준/JAVA] 9655번: 돌 게임
🔺 문제
9655번: 돌 게임
상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.
www.acmicpc.net
🔺 코드
- 풀이1) 재귀를 활용한 풀이
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
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 "";
}
}
|
cs |
- 풀이2) DP를 활용한 풀이
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
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";
}
}
}
}
}
|
cs |
✅ 해결 아이디어
✔ DP
1) 테이블 정의하기
- rock[i] = name : DP 배열 rock의 i번째 값은 name
2) 점화식 세우기
3) 초기값 설정하기
- N의 크기가 1이라면, N[1] = "SK"
- N의 크기가 2라면, N[2] = "CY";
🔺 다른 풀이들
- 찢는 풀이 발견... 🙊🙊🙊
[BOJ] 백준 9655번 : 돌 게임 (JAVA)
문제 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사
steady-coding.tistory.com
- 나도 이렇게 풀었어야 했는데,,^^
[백준] 9655번 : 돌 게임 – JAVA [자바]
https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 문제 문제 풀이 백준 9655번 돌 게임은 DP (다이나믹 프로그래밍)를 이
propercoding.tistory.com
- 멋진 boolean 풀이..
[백준 9655번] 돌 게임 Java 풀이
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. 문제 2. 입력 3. 출력 4. 예제 5. 풀이 이번 문제
small-stap.tistory.com
💬 느낀 점
규칙만 발견하면 되는 것인데..
굉장히 비효율적으로 풀어버렸다 음하하...
담엔 더 단순하게 가보는걸로...
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V | 240309 |
(+ 240309 2회독 : 14376KB, 124s)
dp 안 쓰고 그냥 이렇게 풀어도 맞긴 했다....
문제의 의도는 이게 아닌 것 같지만...
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
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");
}
}
|
cs |
