[BOJ] 1039. 교환 - (Java)

Problem

제출일 : 2020-03-21

문제 풀이 시간 : 2H

난이도 : ★★★

---

link : https://www.acmicpc.net/problem/9019

0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.

1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

Input

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

Output

첫째 줄에 문제에 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 K번 할 수 없으면 -1을 출력한다.

Example

input

16375 1

output

76315

Solution & Inpression

visit을 2차원 배열을 이용하여 처리

BFS를 이용한 완전탐색.

Code

언어 : JAVA

메모리 : 55052 kb

실행 시간 : 176 ms

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    static boolean visit[][];
    static int N, K, len;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        len = ("" + N).length();

        visit = new boolean[1000001][K + 1];

        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { N, 0 });
        visit[N][0] = true;

        int result = -1;

        while (!q.isEmpty()) {
            int[] now = q.poll();

            if (now[1] == K) {
                if (result < now[0]) {
                    result = now[0];
                }
                continue;
            }

            for (int i = 0; i < len - 1; i++) {
                for (int j = i + 1; j < len; j++) {
                    int next = solve(now[0], i, j);
                    if (next != -1 && !visit[next][now[1] + 1]) {
                        visit[next][now[1] + 1] = true;
                        q.add(new int[] { next, now[1] + 1 });
                    }
                }
            }

        }

        System.out.println(result);

    }

    private static int solve(int x, int i, int j) {
        char[] input = ("" + x).toCharArray();

        if (i == 0 && input[j] == '0')
            return -1;

        char tmp = input[i];
        input[i] = input[j];
        input[j] = tmp;

        int ret = 0;
        for (int k = 0; k < input.length; k++) {
            ret *= 10;
            ret += input[k] - '0';
        }
        return ret;
    }
}

[BOJ] 1072. 게임 - (Java)

Problem

제출일 : 2020-03-17

문제 풀이 시간 : 1H 45M

난이도 : ★★★

---

link : https://www.acmicpc.net/problem/1072

김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.

이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.

게임 기록은 다음과 같이 생겼다.

• 게임 횟수 : X
• 이긴 게임 : Y (Z %)
• Z는 형택이의 승률이다. 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z = 88이다.

X와 Y가 주어졌을 때, 형택이가 게임을 몇 판 더해야 Z가 변하는지 구하는 프로그램을 작성하시오.

Input

각 줄에 X와 Y가 주어진다. X는 1,000,000,000보다 작거나 같은 자연수이고, Y는 0보다 크거나 같고, X보다 작거나 같은 자연수이다.

Output

첫째 줄에 형택이가 게임을 몇 판 해야하는지 출력한다. 만약 Z가 절대 변하지 않는다면 -1을 출력한다.

Example

input

10 8

output

1

Solution & Inpression

이분탐색을 이용한 구현

자료형을 주의하여 문제를 해결해야 한다.

99% 와 100%는 확률이 변하지 않음.

Code

언어 : JAVA

메모리 : 14264 kb

실행 시간 : 104 ms

import java.util.Scanner;

public class Main {
    static long X, Y, Z;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        X = sc.nextInt();
        Y = sc.nextInt();

        Z = Y * 100 / X;
        if (Z >= 99)
            System.out.println(-1);
        else
            binarySearch(1, X);
    }

    private static void binarySearch(long start, long end) {
        long mid = 0, ratio = 0;
        while (start <= end) {
            mid = (start + end) / 2;
            ratio = (Y + mid) * 100 / (X + mid);

            if (ratio > Z) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        System.out.println(start);
    }

}

[BOJ] 7453. 합이 0인 네 정수 - (Java)

Problem

제출일 : 2020-03-17

문제 풀이 시간 : 1H

난이도 : ★★★★

---

link : https://www.acmicpc.net/problem/7453

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

Input

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 $2^{28}$이다.

Output

합이 0이 되는 쌍의 개수를 출력한다.

Example

input

6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

output

5

Solution & Inpression

low_bound와 upper_bound를 활용하는 문제, 아이디어를 도출해 내는 것이 중요함.

시간초과를 벗어나기 위해 BufferedReader를 사용했으며 ArrayList대신 배열을 이용함.

Code

언어 : JAVA

메모리 : 140708 kb

실행 시간 : 2552 ms

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[][] data;
    static int[] AB, CD;
    static long ans;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());

        data = new int[4][N];
        for (int j = 0; j < N; j++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < 4; i++) {
                data[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        AB = new int[N * N];
        CD = new int[N * N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                AB[i * N + j] = data[0][i] + data[1][j];
                CD[i * N + j] = data[2][i] + data[3][j];
            }
        }

        Arrays.sort(CD);

        for (int i : AB) {
            int high = upper_bound(CD, -i);
            int low = lower_bound(CD, -i);
            ans += high - low;
        }

        System.out.println(ans);
    }

    // lower bound는 찾고자 하는 값 이상이 처음 나타나는 위치
    private static int lower_bound(int[] arr, int val) {
        int start = 0;
        int end = arr.length;
        int mid;
        while (start < end) {
            mid = (start + end) >> 1;
            if (arr[mid] >= val) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    // upper bound는 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치
    private static int upper_bound(int[] arr, int val) {
        int start = 0;
        int end = arr.length;
        int mid;
        while (start < end) {
            mid = (start + end) >> 1;
            if (arr[mid] <= val) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }
}

[BOJ] 2143. 두 배열의 합 - (Java)

Problem

제출일 : 2020-03-17

문제 풀이 시간 : 1H

난이도 : ★★★★

---

link : https://www.acmicpc.net/problem/2143

한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.

예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.

T(=5) = A[1] + B[1] + B[2]
      = A[1] + A[2] + B[1]
      = A[2] + B[3]
      = A[2] + A[3] + B[1]
      = A[3] + B[1] + B[2]
      = A[3] + A[4] + B[3]
      = A[4] + B[2] 

Input

첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다.

Output

첫째 줄에 답을 출력한다. 가능한 경우가 한 가지도 없을 경우에는 0을 출력한다.

Example

input

5
4
1 3 1 2
3
1 3 2

output

7

Solution & Inpression

low_bound와 upper_bound를 활용하는 문제, 아이디어를 도출해 내는 것이 중요함.

Code

언어 : JAVA

메모리 : 48848 kb

실행 시간 : 948 ms

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int T, N, M;
    static long ans;
    static int[] A, B;

    static List<Integer> a, b;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt(); // T(-1,000,000,000 ≤ T ≤ 1,000,000,000)

        N = sc.nextInt(); // n(1 ≤ n ≤ 1,000)
        A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt(); // 절댓값이 1,000,000을 넘지 않는 정수
        }

        M = sc.nextInt();// m(1≤m≤1,000)
        B = new int[M];
        for (int i = 0; i < M; i++) {
            B[i] = sc.nextInt(); // 절댓값이 1,000,000을 넘지 않는 정수
        }

        a = new ArrayList<>();
        get(A, a);
        b = new ArrayList<>();
        get(B, b);

        Collections.sort(b);

        ans = 0;
        for (Integer i : a) {
            int val = T - i;
            int high = upper_bound(b, val);
            int low = lower_bound(b, val);
            ans += high - low;
        }
        System.out.println(ans);
    }

    private static void get(int[] data, List<Integer> list) {
        for (int size = 1; size <= data.length; size++) {
            int sum = 0;
            for (int i = 0; i < size; i++) {
                sum += data[i];
            }
            for (int i = size; i < data.length; i++) {
                list.add(sum);
                sum += data[i];
                sum -= data[i - size];
            }
            list.add(sum);
        }
    }

    // lower bound는 찾고자 하는 값 이상이 처음 나타나는 위치
    private static int lower_bound(List<Integer> list, int val) {
        int start = 0;
        int end = list.size();
        int mid;
        while (start < end) {
            mid = (start + end) >> 1;
            if (list.get(mid) >= val) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    // upper bound는 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치
    private static int upper_bound(List<Integer> list, int val) {
        int start = 0;
        int end = list.size();
        int mid;
        while (start < end) {
            mid = (start + end) >> 1;
            if (list.get(mid) <= val) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }
}

[BOJ] 1208. 부분수열의 합 2 - (Java)

Problem

제출일 : 2020-03-16

문제 풀이 시간 : 5H

난이도 : ★★★★★

---

link : https://www.acmicpc.net/problem/1208

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

Input

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

Output

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

Example

input

5 0
-7 -3 -2 5 8

output

1

Solution & Inpression

1182. 부분수열의 합문제에서 N이 40까지 커진문제...

여러 블로그를 보며 문제에 해답을 얻고 문제를 해결했다.

문제를 해결한 아이디어는 주어진 입력을 절반씩 나누어 A, B로 구분을 했을때 A와 B는 최대 20개의 숫자를 갖는다. A와 B의 모든 부분수열의 합을 List에 저장을 하였다. (N=20은 주어진 시간내에 완전 탐색이 가능하다.)

부분 수열의 합이 S가 되는 경우는

1. A List의 값이 S 인 경우
2. B List의 값이 S 인 경우
3. A List의 값이 x라 할 때 B List 값이 S-x 인 경우

로 총 3가지의 경우 합이다.

C에 algorithm 라이브러리에 포함된 함수인 lower_bound와 upper_bound를 구현해 문제를 해결했다.

따로 위 함수들은 정리하겠다.

long ans: 모든 경우의 수는 $2^{40}$으로 int형을 사용하면 범위가 초과하니 주의 해야한다.

Code

언어 : JAVA

메모리 : 83140 kb

실행 시간 : 1360 ms

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    static int N, S;
    static int ans; // int :2^32 long: 2^64 >> 문제: 2^40
    static int[] input;
    static ArrayList<Integer> L, R;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        S = sc.nextInt();
        input = new int[N];
        for (int i = 0; i < N; i++) {
            input[i] = sc.nextInt();
        }

        L = new ArrayList<>();
        R = new ArrayList<>();
        solve(0, N / 2, 0, L);
        solve(N / 2, N, 0, R);

        Collections.sort(R);

        ans = 0;
        for (int val : L) {
            val = S - val;
            int hi = upper_bound(R, val);
            int lo = lower_bound(R, val);
            ans += hi - lo;
        }

        // 공집합 제거
        if (S == 0) {
            --ans;
        }
        System.out.println(ans);
    }

    // lower bound는 찾고자 하는 값 이상이 처음 나타나는 위치
    private static int lower_bound(ArrayList<Integer> list, int val) {
        int start = 0;
        int end = list.size();
        int mid;
        while (start < end) {
            mid = (start + end) >> 1;
            if (list.get(mid) >= val) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    // upper bound는 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치
    private static int upper_bound(ArrayList<Integer> list, int val) {
        int start = 0;
        int end = list.size();
        int mid;
        while (start < end) {
            mid = (start + end) >> 1;
            if (list.get(mid) <= val) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }

    // 범위에 해당하는 모든 부분수열의 합을 저장.
    private static void solve(int pos, int end, int sum, ArrayList<Integer> list) {
        if (pos == end) {
            list.add(sum);
            return;
        }
        solve(pos + 1, end, sum, list);
        solve(pos + 1, end, sum + input[pos], list);
    }

}

Reference

http://joonas-yoon.blogspot.com/2016/03/1208-2.html

https://23dotory.tistory.com/27

[BOJ] 1806. 부분합 - (Java)

Problem

제출일 : 2020-03-15

문제 풀이 시간 : 20M

난이도 : ★★

---

link : https://www.acmicpc.net/problem/1806

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

Input

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

Output

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

Example

input

4 2
1 1 1 1

output

3

Solution & Inpression

2003. 수들의 합 2응용 문제

주의 해야 할 점은 부분합 중에 그 합이 S 이상이 되는 것으로 정확히 일치하는 것이 아닌 이상이 되는 값을 찾아야 함!!!!

Code

언어 : JAVA

메모리 : 90640 kb

실행 시간 : 684 ms

import java.util.Scanner;

public class Main {

    static int N, S, ans, sum;
    static int[] data;
    static int s, e;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        S = sc.nextInt();

        data = new int[N + 1];
        for (int i = 0; i < N; i++) {
            data[i] = sc.nextInt();
        }

        ans = Integer.MAX_VALUE;
        s = 0;
        e = 0;
        while (e <= N && s <= N) {
            if (sum >= S && ans > e - s)
                ans = e - s;

            if (sum < S)
                sum += data[e++];
            else
                sum -= data[s++];
        }
        System.out.println(ans == Integer.MAX_VALUE ? 0 : ans);
    }
}

[BOJ] 2003. 수들의 합 2 - (Java)

Problem

제출일 : 2020-03-15

문제 풀이 시간 : 20M

난이도 : ★

---

link : https://www.acmicpc.net/problem/12100

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i]+A[i+1]+…+A[j-1]+A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

Input

첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

Output

첫째 줄에 경우의 수를 출력한다.

Example

input

4 2
1 1 1 1

output

3

Solution & Inpression

완전탐색? 포인터의 활용..

code 1 : 처음 문제를 풀 때 한번에 더할 개수를 정하고 그 수만큼 더한 모든 경우의 수를 탐색했다.

code 2 : code 1의 최적화 버전으로 양쪽에 포인터를 두어 목표 값보다 작다면 값을 더하고 작으면 값을 빼는 방법으로 굳이 검사하지 않아도 되는 부분을 검사하지 않을 수 있어 속도가 더욱 빠른 코드이다.

Code 1

언어 : JAVA

메모리 : 26960 kb

실행 시간 : 440 ms

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N, M, ans;
    static int[] data;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        data = new int[N];
        for (int i = 0; i < N; i++) {
            data[i] = sc.nextInt();
        }

        ans = 0;
        for (int i = 1; i <= N; i++) {
            solve(i);
        }
        System.out.println(ans);
    }

    private static void solve(int size) {
        int sum = 0;
        for (int i = 0; i < size; i++) {
            sum += data[i];
        }

        for (int i = size; i < N; i++) {
            if (sum == M)
                ans++;
            sum += data[i];
            sum -= data[i - size];
        }
        if (sum == M)
            ans++;
    }
}

Code 2

언어 : JAVA

메모리 : 27320 kb

실행 시간 : 244 ms

import java.util.Scanner;

public class Main {

    static int N, M, ans, sum;
    static int[] data;
    static int s, e;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        data = new int[N + 1];
        for (int i = 0; i < N; i++) {
            data[i] = sc.nextInt();
        }
        s = 0;
        e = 0;

        while (e <= N) {
            if (sum == M)
                ans++;

            if (sum < M)
                sum += data[e++];
            else
                sum -= data[s++];
        }

        System.out.println(ans);

    }

}

[BOJ] 12100. 2048 (Easy) - (Java)

Problem

제출일 : 2020-03-15

문제 풀이 시간 : 1H

난이도 : ★★★

---

link : https://www.acmicpc.net/problem/12100

2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다.

이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다)

<그림 1>	<그림 2>	<그림 3>

<그림 1>의 경우에서 위로 블록을 이동시키면 <그림 2>의 상태가 된다. 여기서, 왼쪽으로 블록을 이동시키면 <그림 3>의 상태가 된다.

<그림 4>	<그림 5>	<그림 6>	<그림 7>

<그림 4>의 상태에서 블록을 오른쪽으로 이동시키면 <그림 5>가 되고, 여기서 다시 위로 블록을 이동시키면 <그림 6>이 된다. 여기서 오른쪽으로 블록을 이동시켜 <그림 7>을 만들 수 있다.

<그림 8>	<그림 9>

<그림 8>의 상태에서 왼쪽으로 블록을 옮기면 어떻게 될까? 2가 충돌하기 때문에, 4로 합쳐지게 되고 <그림 9>의 상태가 된다.

<그림 10>	<그림 11>	<그림 12>	<그림 13>

<그림 10>에서 위로 블록을 이동시키면 <그림 11>의 상태가 된다.

<그림 12>의 경우에 위로 블록을 이동시키면 <그림 13>의 상태가 되는데, 그 이유는 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐질 수 없기 때문이다.

<그림 14>	<그림 15>

마지막으로, 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 예를 들어, 위로 이동시키는 경우에는 위쪽에 있는 블록이 먼저 합쳐지게 된다. <그림 14>의 경우에 위로 이동하면 <그림 15>를 만든다.

이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

Input

첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다.

Output

최대 5번 이동시켜서 얻을 수 있는 가장 큰 블록을 출력한다.

Example

input

3
2 2 2
4 4 4
8 8 8

output

16

Solution & Inpression

시뮬레이션 + 완전 탐색

모든 경우의 수를 탐색하는 완전 탐색 시뮬레이션 문제

인덱스 조작이 까다로워 ArrayList를 사용하여 문제를 해결하였다. 움직이는 방향에 따라 list에 값을 넣는 순서를 바꾸어 작업했다.

list[i].get(0).equals(list[i].get(1))이렇게 두 수가 합쳐질 수 있는지 검사하였는데 처음 코드는

list[i].get(0)==list[i].get(1)이었는데 왜 인지 모르게 틀렸다. 왜 지?????

Code

언어 : JAVA

메모리 : 44464 kb

실행 시간 : 736 ms

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static int N, ans;
    static int[][] map;
    static int[] data;
    static ArrayList<Integer>[] list;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        map = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        ans = 0;
        data = new int[5];

        list = new ArrayList[N];
        for (int i = 0; i < N; i++) {
            list[i] = new ArrayList<>();
        }
        solve(0, 0);
        System.out.println(ans);

    }

    private static void solve(int index, int depth) {
        if (depth == 5) {
            check();
            return;
        }
        for (int i = 0; i < 4; i++) {
            if (data[depth] == 0) {
                data[depth] = i;
                solve(index, depth + 1);
                data[depth] = 0;
            }
        }
    }

    private static void check() {
        int[][] copy = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                copy[i][j] = map[i][j];
            }
        }

        for (int time = 0; time < 5; time++) {
            switch (data[time]) {
            case 0: // 상
                for (int r = 0; r < N; r++) {
                    for (int c = 0; c < N; c++) {
                        if (copy[r][c] != 0) {
                            list[c].add(copy[r][c]);
                            copy[r][c] = 0;
                        }
                    }
                }
                for (int i = 0; i < N; i++) {
                    int r = 0;
                    while (list[i].size() != 0) {
                        if (list[i].size() != 1 && list[i].get(0).equals(list[i].get(1))) {
                            copy[r++][i] = list[i].get(0) << 1;
                            list[i].remove(0);
                            list[i].remove(0);
                        } else {
                            copy[r++][i] = list[i].get(0);
                            list[i].remove(0);
                        }
                    }
                }
                break;

            case 1: // 하
                for (int r = N - 1; r >= 0; r--) {
                    for (int c = 0; c < N; c++) {
                        if (copy[r][c] != 0) {
                            list[c].add(copy[r][c]);
                            copy[r][c] = 0;
                        }
                    }
                }

                for (int i = 0; i < N; i++) {
                    int r = N - 1;
                    while (list[i].size() != 0) {
                        if (list[i].size() != 1 && list[i].get(0).equals(list[i].get(1))) {
                            copy[r--][i] = list[i].get(0) << 1;
                            list[i].remove(0);
                            list[i].remove(0);
                        } else {
                            copy[r--][i] = list[i].get(0);
                            list[i].remove(0);
                        }
                    }
                }
                break;
            case 2: // 좌
                for (int r = 0; r < N; r++) {
                    for (int c = 0; c < N; c++) {
                        if (copy[r][c] != 0) {
                            list[r].add(copy[r][c]);
                            copy[r][c] = 0;
                        }
                    }
                }

                for (int i = 0; i < N; i++) {
                    int c = 0;
                    while (list[i].size() != 0) {
                        if (list[i].size() != 1 && list[i].get(0).equals(list[i].get(1))) {
                            copy[i][c++] = list[i].get(0) << 1;
                            list[i].remove(0);
                            list[i].remove(0);
                        } else {
                            copy[i][c++] = list[i].get(0);
                            list[i].remove(0);
                        }
                    }
                }
                break;
            case 3: // 우
                for (int r = 0; r < N; r++) {
                    for (int c = N - 1; c >= 0; c--) {
                        if (copy[r][c] != 0) {
                            list[r].add(copy[r][c]);
                            copy[r][c] = 0;
                        }
                    }
                }

                for (int i = 0; i < N; i++) {
                    int c = N - 1;
                    while (list[i].size() != 0) {
                        if (list[i].size() != 1 && list[i].get(0).equals(list[i].get(1))) {
                            copy[i][c--] = list[i].get(0) << 1;
                            list[i].remove(0);
                            list[i].remove(0);
                        } else {
                            copy[i][c--] = list[i].get(0);
                            list[i].remove(0);
                        }
                    }
                }
                break;
            }// end of switch
        }

        int max = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (max < copy[i][j])
                    max = copy[i][j];
            }
        }

        if (ans < max)
            ans = max;

    }
}