반응형
Notice
Recent Posts
Recent Comments
Link
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
Tags
- 자바개념
- java
- 백준9단계
- 무료개발강의
- 빅오 표기법
- ☆
- dp
- 무료코딩강의
- 자바의정석연습문제풀이
- 개발공부
- 알고리즘
- 자바
- 백준알고리즘
- 동적계획법
- 시간 복잡도
- 백준단계별로풀어보기
- 다이나믹 프로그래밍
- 자바공부
- Java개념
- 브루트포스
- 코딩공부
- 백준자바
- dfs
- 백준
- BFS
- 백트래킹
- 알고리즘공부
- ★
- 자바의정석연습문제
- 자바의정석
Archives
- Today
- Total
더 많이 실패하기
공부 147일차: 백준 3085번 사탕 게임 자바 java 본문
반응형
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 |
알고리즘 떠올라서 재밌었고
그것 외에도 방법이 더 있어서 좋았다
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| 공부 149일차: 백준 1107번 리모컨 자바 java (0) | 2022.12.26 |
|---|---|
| 공부 148일차: 백준 1476번 날짜 계산 자바 java (0) | 2022.12.25 |
| 공부 146일차: 백준 2309번 일곱 난쟁이 자바 java (0) | 2022.12.23 |
| 공부 145일차: 백준 17404번 RGB거리 2 자바 java (0) | 2022.12.22 |
| 공부 144일차: 백준 2133번 타일 채우기 자바 java (0) | 2022.12.21 |
'알고리즘/백준' Related Articles
more
Comments