1. 문제
https://www.acmicpc.net/problem/12100
2. 풀이 과정
처음엔 쉬운 풀이 방법이 있을까 생각하다가, 안 떠올라서 그냥 모든 경우의 수를 다 돌려보고 생각해봐야겠다 하고 구현했는데, 통과가 되었다.
위로, 아래로, 왼쪽으로, 오른쪽으로 각각 0, 1, 2, 3으로 생각하고 5개를 뽑는 중복 순열을 만들었다. 선택한 차례대로 함수를 실행시켜 결과를 냈다.
1) 최대값 구하기
- 처음 값을 입력받을 때, 확인
- 두 값이 같아서 합칠 때, 확인
=> 두 경우만 고려하면 된다.
2) 네 방향 중 하나로 이동시키기
- 자신이 앞으로 갈 수 있는 위치 = prev
- 지금 보고 있는 위치 = j
단계 1) Up, Down, Left, Right를 따로 생성
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Boj12100 {
static int N, max;
static int order[], origin[][];
public static void permutation(int cnt) {
if(cnt==5) {
//배열 복사
int[][] carr = new int[N][N];
for(int i=0;i<N;i++)
carr[i] = origin[i].clone();
for(int i=0;i<5;i++) {
switch(order[i]) {
case 0:
goUp(carr);
break;
case 1:
goDown(carr);
break;
case 2:
goLeft(carr);
break;
case 3:
goRight(carr);
break;
}
}
return;
}
for(int i=0;i<4;i++) {//4방향 up, down, left, right
order[cnt]=i;
permutation(cnt+1);
}
}
public static void goUp(int arr[][]) {
for(int i=0;i<N;i++) {
int prev = 0;
for(int j=1;j<N;j++) {
if(arr[j][i]==0) {
continue;
}
else {
if(arr[prev][i]==0) {
arr[prev][i] = arr[j][i];
arr[j][i] = 0;
}
else {
if(arr[prev][i] == arr[j][i]) {//값이 같으면
arr[prev][i]*=2;
arr[j][i] = 0;
max = Math.max(max, arr[prev][i]);
prev++;
}
else {
if(++prev != j) {
arr[prev][i] = arr[j][i];
arr[j][i] = 0;
}
}
}
}
}
}
}
public static void goDown(int arr[][]) {
for(int i=0;i<N;i++) {
int prev = N-1;
for(int j=N-2;j>=0;j--) {
if(arr[j][i]==0) {
continue;
}
else {
if(arr[prev][i]==0) {
arr[prev][i] = arr[j][i];
arr[j][i] = 0;
}
else {
if(arr[prev][i] == arr[j][i]) {//값이 같으면
arr[prev][i]*=2;
arr[j][i] = 0;
max = Math.max(max, arr[prev][i]);
prev--;
}
else {
if(--prev != j) {
arr[prev][i] = arr[j][i];
arr[j][i] = 0;
}
}
}
}
}
}
}
public static void goLeft(int arr[][]) {
for(int i=0;i<N;i++) {
int prev = 0;
for(int j=1;j<N;j++) {
if(arr[i][j]==0) {
continue;
}
else {
if(arr[i][prev]==0) {
arr[i][prev] = arr[i][j];
arr[i][j] = 0;
}
else {
if(arr[i][prev] == arr[i][j]) {//값이 같으면
arr[i][prev]*=2;
arr[i][j] = 0;
max = Math.max(max, arr[i][prev]);
prev++;
}
else {
if(++prev != j) {
arr[i][prev] = arr[i][j];
arr[i][j] = 0;
}
}
}
}
}
}
}
public static void goRight(int arr[][]) {
for(int i=0;i<N;i++) {
int prev = N-1;
for(int j=N-2;j>=0;j--) {
if(arr[i][j]==0) {
continue;
}
else {
if(arr[i][prev]==0) {
arr[i][prev] = arr[i][j];
arr[i][j] = 0;
}
else {
if(arr[i][prev] == arr[i][j]) {//값이 같으면
arr[i][prev]*=2;
arr[i][j] = 0;
max = Math.max(max, arr[i][prev]);
prev--;
}
else {
if(--prev != j) {
arr[i][prev] = arr[i][j];
arr[i][j] = 0;
}
}
}
}
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
origin = new int[N][N];
order = new int[5];//방향 5개 선택
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
origin[i][j] = Integer.parseInt(st.nextToken());
max = Math.max(max, origin[i][j]);
}
}
permutation(0);
System.out.println(max);
}
}
단계 2) Up&Down과 Left&Right를 하나로 묶음
묶은 기준은 2차원 배열의 접근 방식이다 Up&Down은 모두 arr[i][j]로 한 열씩 탐색한다면,
Left&Right은 arr[j][i]로 한 행씩 차례로 탐색한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Boj12100_2 {
static int N, max;
static int order[], origin[][];
public static void permutation(int cnt) {
if(cnt==5) {
//배열 복사
int[][] carr = new int[N][N];
for(int i=0;i<N;i++)
carr[i] = origin[i].clone();
for(int i=0;i<5;i++)
move(order[i], carr);
return;
}
for(int i=0;i<4;i++) {//4방향 up, down, left, right
order[cnt]=i;
permutation(cnt+1);
}
}
public static void move(int n, int arr[][]) {
//up, down, left, right
int start = (n%2==0) ? 0 : N-1;
int inc = (n%2==0) ? 1 : -1;
if(n<2) {//up & down
for(int i=0;i<N;i++) {
int prev = start;
for(int j=start+inc; 0<=j && j<N; j+=inc) {
if(arr[j][i]==0) {
continue;
}
else {
if(arr[prev][i]==0) {
arr[prev][i] = arr[j][i];
arr[j][i] = 0;
}
else {
if(arr[prev][i] == arr[j][i]) {//값이 같으면
arr[prev][i]*=2;
arr[j][i] = 0;
max = Math.max(max, arr[prev][i]);
prev+=inc;
}
else {
prev+=inc;
if(prev != j) {
arr[prev][i] = arr[j][i];
arr[j][i] = 0;
}
}
}
}
}
}
}
else {//left & right
for(int i=0;i<N;i++) {
int prev = start;
for(int j=start+inc; 0<=j && j<N; j+=inc) {
if(arr[i][j]==0) {
continue;
}
else {
if(arr[i][prev]==0) {
arr[i][prev] = arr[i][j];
arr[i][j] = 0;
}
else {
if(arr[i][prev] == arr[i][j]) {//값이 같으면
arr[i][prev]*=2;
arr[i][j] = 0;
max = Math.max(max, arr[i][prev]);
prev+=inc;
}
else {
prev += inc;
if(prev != j) {
arr[i][prev] = arr[i][j];
arr[i][j] = 0;
}
}
}
}
}
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
N = Integer.parseInt(br.readLine());
origin = new int[N][N];//벽세움
order = new int[5];//방향 5개 선택
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
origin[i][j] = Integer.parseInt(st.nextToken());
max = Math.max(max, origin[i][j]);
}
}
permutation(0);
System.out.println(max);
}
}
'코딩문제풀이 > Baekjoon' 카테고리의 다른 글
[Java] 백준 4485번 : 녹색 옷 입은 애가 젤다지? (0) | 2022.04.01 |
---|---|
[Java] 백준 2133번 : 타일 채우기 (0) | 2022.04.01 |
[Java] 백준 17404번 : RGB거리 2 (0) | 2022.03.27 |
[Java] 백준 1300: K번째 수 (0) | 2022.03.22 |
[Java] 백준 2206번 : 벽 부수고 이동하기 (0) | 2022.03.20 |