백준 17351 JAVA : 3루수는 몰라

문제

https://www.acmicpc.net/problem/17351

17351번: 3루수는 몰라

 

풀이 예상

알파벳 순서대로 M, O, L, A 를 1, 2, 3, 4 로 두고 점점 증가시킨다.

MOLA가 하나 완성되었다면 다음 M, O, L, A의 값은 5, 6, 7, 8 이다. 이 것을 반복하다보면

M을 나머지연산하면 1, O를 나머지연산하면 2, L를 나머지연산하면 3, A를 나머지연산하면 4 가 된다.

 

이러한 방법을 이용해서 dp배열을 갱신한다.

이동할 때, 오른쪽방향과 아래방향으로밖에 못움직이기 때문에

현재 방향에서 이전 방향인 것은 왼쪽과 위쪽밖에 없다. 이 점을 이용해서 모든 맵을 돌면서 왼쪽과 위쪽을 확인하면서 갱신하면 된다.

 

각각의 칸에서 아래와 같은 작업을 한다.

1. 왼쪽과 위쪽 칸의 최댓값을 지금의 칸에 넣는다.

2. MOLA 칸이라면 이전 칸과 지금칸이 연속되어있는지 확인하는 로직을 한다.

  2-1. M 알파벳이라면 지금까지 MOLA개수 x 4 +1 값으로 초기화한다. => 새로운 M의 시작

  2-2. OLA 알파벳이라면, 이어지는 문자가 없을 시 MOLA개수 x 4 값으로 초기화한다.

  2-3. 이어지는 문자가 있을 시 MOLA 문자개수를 비교하고, 이어질때의 MOLA문자개수가 크거나 같다면 값을 갱신한다.

3. MOLA가 아닌 알파벳이라면 초기화한다. (지금까지 MOLA개수 x 4 값으로)

 

풀이방법 (접근 방법 & 시간복잡도)

시간복잡도 => O(N^2)

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static String str;
    static char c;
    static int[][] ground;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ground = new int[N+1][N+1];

        for (int i = 0; i <= N; i++) {
            ground[0][i] = -1;
        }
        for (int i = 0; i <= N; i++) {
            ground[i][0] = -1;
        }

        for (int i = 1; i <= N; i++) {
            str = br.readLine();
            for (int j = 1; j <= N ; j++) {
                //위랑 왼쪽 보고 최댓값 갱신
                c = str.charAt(j-1);

                //지금까지 최댓값 갱신
                ground[i][j] = Math.max(ground[i-1][j], ground[i][j-1]);

                if(c == 'M') {
                    ground[i][j] = ground[i][j] / 4 * 4 +1;

                }else if(c == 'O') {
                    check(i, j, 1);
                }else if(c == 'L') {
                    check(i, j, 2);
                }else if(c == 'A') {
                    check(i, j, 3);
                }else {
                    ground[i][j] = ground[i][j] / 4 * 4;
                }

            }
        }
        System.out.println(ground[N][N]/4);

    }
    static void check(int i , int j, int num) {
        if(ground[i-1][j] % 4 != num && ground[i][j-1] % 4 != num) {
            //이어지는 문자가 없을때
            ground[i][j] = ground[i][j] / 4 * 4;
            return;
        }
        int countBefore = ground[i][j] / 4;
        int countAfter = 0;

        if(ground[i-1][j] % 4 == num) {
            countAfter = (ground[i-1][j]+1) / 4;
            if(countAfter >= countBefore) { //MOLA 만든 횟수가 크거나 같으면
                ground[i][j] = ground[i-1][j]+1;
            }
        }
        if(ground[i][j-1] % 4 == num) {
            countAfter = (ground[i][j-1]+1) / 4;
            if(countAfter >= countBefore) { //MOLA 만든 횟수가 크거나 같으면
                ground[i][j] = ground[i][j-1]+1;
            }
        }

        if(ground[i-1][j] % 4 == num && ground[i][j-1] % 4 == num) {
            countAfter = Math.max((ground[i-1][j]+1) / 4, (ground[i][j-1]+1) / 4);
            if(countAfter >= countBefore) { //MOLA 만든 횟수가 크거나 같으면
                ground[i][j] = Math.max(ground[i-1][j]+1, ground[i][j-1]+1);
            }
        }

    }
}

 

결과