알고리즘/백준
공부 147일차: 백준 3085번 사탕 게임 자바 java
김발자~
2022. 12. 24. 21:16
반응형
3085 사탕 게임
https://www.acmicpc.net/problem/3085
3085번: 사탕 게임
예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.
www.acmicpc.net
백준 3085번 문제 사탕 게임
문제
과정 생각해보기 & 오답
인접한 사탕이 다를 때 바꾼다고 했으므로 상황은1) 가로로 바꿀 때 2) 세로로 바꿀 때로 나뉜다
그림에서 보았듯이 가로로 바꾸면 2열, 1행이 달라지고세로로 바꾸면 1열, 2행이 달라진다
그걸 고려해서 짜본 코드
|
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
import java.io.*;
import java.util.Arrays;
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());
char[][] candies = new char[n][n];
for(int i = 0; i < n; i++) {
String row = br.readLine();
for(int j = 0; j < n; j++) {
candies[i][j] = row.charAt(j);
}
}
// 디버깅
//System.out.println(Arrays.deepToString(candies));
int max = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n-1; j++) {
// 오른쪽이랑 다르다면 (가로로 바꾸기)
if(candies[i][j] != candies[i][j+1]) {
// 바꾸기
char temp = candies[i][j];
candies[i][j] = candies[i][j+1];
candies[i][j+1] = temp;
// 바꾼 그 행 확인
int count = 1;
for(int l = 0; l < n-1; l++) {
//System.out.println("candies["+i+"]["+l+"] : "+candies[i][l]+", candies["+i+"]["+(l+1)+"] : "+candies[i][l+1]);
if(candies[i][l] == candies[i][l+1]) {
count++;
}else {
count = 1;
}
max = Math.max(max, count);
}
// j, j+1 포함한 열 2개 확인
for(int k = 0; k < n-1; k++) {
count = 1;
for(int l = j; l < j+2; l++) {
if(j+1 < n) {
if(candies[k][l] == candies[k+1][l]) {
count++;
}else {
count = 1;
}
max = Math.max(max, count);
}
}
}
// 바꿨던 것 돌려놓기
temp = candies[i][j];
candies[i][j] = candies[i][j+1];
candies[i][j+1] = temp;
}
}
}
for(int i = 0; i < n-1; i++) {
for(int j = 0; j < n; j++) {
// 아래랑 다르다면 (세로로 바꾸기)
if(candies[i][j] != candies[i+1][j]) {
// 바꾸기
char temp = candies[i][j];
candies[i][j] = candies[i+1][j];
candies[i+1][j] = temp;
// 바꾼 그 열 확인
int count = 1;
for(int l = 0; l < n-1; l++) {
if(candies[l][j] == candies[l+1][j]) {
count++;
}else {
count = 1;
}
max = Math.max(max, count);
}
// j, j+1 포함한 행 2개 확인
for(int k = 0; k < n-1; k++) {
count = 1;
for(int l = j; l < j+2; l++) {
if(j+1 < n) {
if(candies[l][k] == candies[l][k+1]) {
count++;
}else {
count = 1;
}
max = Math.max(max, count);
}
}
}
// 바꿨던 것 돌려놓기
temp = candies[i][j];
candies[i][j] = candies[i+1][j];
candies[i+1][j] = temp;
}
}
}
System.out.println(max);
}
}
|
cs |
하지만 원하는 답이 나오지 않았다
(바꾸지 않아도 이미 같은 것들끼리만 나열된 줄을 확인하지 않기 때문인 듯하다)
그래서 그냥 바뀔 때마다 전체 행, 열을 확인해보았다
정답 인정 코드
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
|
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());
char[][] candies = new char[n][n];
for(int i = 0; i < n; i++) {
String row = br.readLine();
for(int j = 0; j < n; j++) {
candies[i][j] = row.charAt(j);
}
}
// 디버깅
//System.out.println(Arrays.deepToString(candies));
int max = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n-1; j++) {
// 오른쪽이랑 다르다면 (가로로 바꾸기)
if(candies[i][j] != candies[i][j+1]) {
// 바꾸기
char temp = candies[i][j];
candies[i][j] = candies[i][j+1];
candies[i][j+1] = temp;
// 바꾼 후 확인 1. 가로
for(int k = 0; k < n; k++) {
int count = 1;
for(int l = 0; l < n-1; l++) {
//System.out.println("candies["+k+"]["+l+"] : "+candies[k][l]+", candies["+k+"]["+(l+1)+"] : "+candies[k][l+1]);
if(candies[k][l] == candies[k][l+1]) {
count++;
}else {
count = 1; // 다르다면 다시 1부터 시작
}
max = Math.max(max, count);
}
}
// 2. 세로
for(int k = 0; k < n; k++) {
int count = 1;
for(int l = 0; l < n-1; l++) {
if(candies[l][k] == candies[l+1][k]) {
count++;
}else {
count = 1; // 다르다면 다시 1부터 시작
}
max = Math.max(max, count);
}
}
// 바꿨던 것 돌려놓기
temp = candies[i][j];
candies[i][j] = candies[i][j+1];
candies[i][j+1] = temp;
}
}
}
for(int i = 0; i < n-1; i++) {
for(int j = 0; j < n; j++) {
// 아래랑 다르다면 (세로로 바꾸기)
if(candies[i][j] != candies[i+1][j]) {
// 바꾸기
char temp = candies[i][j];
candies[i][j] = candies[i+1][j];
candies[i+1][j] = temp;
// 바꾼 후 확인 1. 가로
for(int k = 0; k < n; k++) {
int count = 1;
for(int l = 0; l < n-1; l++) {
if(candies[k][l] == candies[k][l+1]) {
count++;
}else {
count = 1; // 다르다면 다시 1부터 시작
}
max = Math.max(max, count);
}
}
// 2. 세로
for(int k = 0; k < n; k++) {
int count = 1;
for(int l = 0; l < n-1; l++) {
if(candies[l][k] == candies[l+1][k]) {
count++;
}else {
count = 1; // 다르다면 다시 1부터 시작
}
max = Math.max(max, count);
}
}
// 바꿨던 것 돌려놓기
temp = candies[i][j];
candies[i][j] = candies[i+1][j];
candies[i+1][j] = temp;
}
}
}
System.out.println(max);
}
}
|
cs |
다른 분들 보니까 가로, 세로 확인하는 게 코드 중복이다 보니 메서드로 바꿔서 쓰신 분이 많았다
2) 메서드 만들어서 쓴 코드
|
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
|
import java.io.*;
import java.util.Arrays;
public class Main {
static int n;
static char[][] candies;
static int max = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
candies = new char[n][n];
for(int i = 0; i < n; i++) {
String row = br.readLine();
for(int j = 0; j < n; j++) {
candies[i][j] = row.charAt(j);
}
}
// 디버깅
//System.out.println(Arrays.deepToString(candies));
max = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n-1; j++) {
// 오른쪽이랑 다르다면 (가로로 바꾸기)
if(candies[i][j] != candies[i][j+1]) {
// 바꾸기
char temp = candies[i][j];
candies[i][j] = candies[i][j+1];
candies[i][j+1] = temp;
check();
// 바꿨던 것 돌려놓기
temp = candies[i][j];
candies[i][j] = candies[i][j+1];
candies[i][j+1] = temp;
}
}
}
for(int i = 0; i < n-1; i++) {
for(int j = 0; j < n; j++) {
// 아래랑 다르다면 (세로로 바꾸기)
if(candies[i][j] != candies[i+1][j]) {
// 바꾸기
char temp = candies[i][j];
candies[i][j] = candies[i+1][j];
candies[i+1][j] = temp;
check();
// 바꿨던 것 돌려놓기
temp = candies[i][j];
candies[i][j] = candies[i+1][j];
candies[i+1][j] = temp;
}
}
}
System.out.println(max);
}
public static int check() {
for(int k = 0; k < n; k++) {
int count = 1;
for(int l = 0; l < n-1; l++) {
if(candies[k][l] == candies[k][l+1]) {
count++;
}else {
count = 1; // 다르다면 다시 1부터 시작
}
max = Math.max(max, count);
}
}
// 2. 세로
for(int k = 0; k < n; k++) {
int count = 1;
for(int l = 0; l < n-1; l++) {
if(candies[l][k] == candies[l+1][k]) {
count++;
}else {
count = 1; // 다르다면 다시 1부터 시작
}
max = Math.max(max, count);
}
}
return max;
}
}
|
cs |
알고리즘 떠올라서 재밌었고
그것 외에도 방법이 더 있어서 좋았다
반응형