글 읽기 - 접근 방법 질문

puzzledpublic 4년 전 0

코드에 주석 적어 놓은대로 해봤습니다.

틀린 예시가 있을까요.

다른 예외가 생각이 안나네요.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		char[][] ground = new char[N + 1][N + 1];
		int[][][] dp = new int[N + 1][N + 1][4];
		for(int i = 1; i <= N; i++) {
			String line = br.readLine();
			for(int j = 1; j <= N; j++) {
				ground[i][j] = line.charAt(j - 1);
			}
		}
        //dp[i][j][0] = (i - 1, j) -> (i, j)로 갈때 MOLA문자가 이어지는지 1로 체크 
        //dp[i][j][1] = (i - 1, j) -> (i, j)로 갈떄 MOLA문자의 최대 개수
        //dp[i][j][2] = (i, j - 1) -> (i, j)로 갈때 MOLA문자가 이어지는지 1로 체크
        //dp[i][j][3] = (i, j - 1) -> (i, j)로 갈때 MOLA문자의 최대 개수
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= N; j++) {
				
				int A = dp[i - 1][j][1];    //(i - 2, j) -> (i - 1, j) 최대 MOLA 개수
				int B = dp[i - 1][j][3];    //(i - 1, j - 1) -> (i - 1, j) 갈때 최대 MOLA 개수
				int C = dp[i][j - 1][1];    //(i - 1, j - 1) -> (i, j - 1) 갈때 최대 MOLA 개수
				int D = dp[i][j - 1][3];    //(i, j - 2) -> (i, j - 1) 갈때 최대 MOLA 개수
				
				if(ground[i][j] == 'O') {    //현재 문자가 'O'이고
					if(ground[i - 1][j] == 'M') {    //위쪽이 'M'
						dp[i][j][0] = 1;    //현재 문자도 이어짐 체크
					}
					if(ground[i][j - 1] == 'M') {    //왼쪽이 'M'
						dp[i][j][2] = 1;
					}
				}else if(ground[i][j] == 'L') {    //현재 문자가 'L'이고
                    //위쪽이 이어지는 'O'가 있는 경우
					if((dp[i - 1][j][0] == 1 && ground[i - 1][j] == 'O') || (dp[i - 1][j][2] == 1 && ground[i - 1][j] == 'O')) {
						dp[i][j][0] = 1;
					}
                    //왼쪽이 이어지는 'O'가 있는 경우
					if((dp[i][j - 1][0] == 1 && ground[i][j - 1] == 'O') || (dp[i][j - 1][2] == 1 && ground[i][j - 1] == 'O')) {
						dp[i][j][2] = 1;
					}
				}else if(ground[i][j] == 'A') {    //현재 문자가 'A'이고
                    //위쪽에서 이어지는 'L'이 있는 경우 (i - 2, j) -> (i - 1, j) -> (i, j)
					if((dp[i - 1][j][0] == 1 && ground[i - 1][j] == 'L')) {
						A++;    //MOLA가 하나 더 추가 됨
					}
                    // (i - 1, j - 1) -> (i - 1, j) -> (i, j)
					if((dp[i - 1][j][2] == 1 && ground[i - 1][j] == 'L')) {
						B++;
					}
                    //왼쪽에서 이어지는 'L'이 있는 경우 (i - 1, j - 1) -> (i, j -1) -> (i, j)
					if((dp[i][j - 1][0] == 1 && ground[i][j - 1] == 'L')) {
						C++;
					}
                    // (i, j - 2) -> (i, j - 2) -> (i, j)
					if((dp[i][j - 1][2] == 1 && ground[i][j - 1] == 'L')) {
						D++;
					}
				}
				dp[i][j][1] = Math.max(A, B);    //(i, j)기준 위쪽에서 올때 MOLA의 최대 개수
				dp[i][j][3] = Math.max(C, D);    //왼쪽에서 올때 MOLA의 최대 개수
			}
		}
		
		bw.write(Math.max(dp[N][N][1], dp[N][N][3]) + "\n");    //(N,N) 위치의 MOLA의 최대 개수

		bw.flush();
		bw.close();
		br.close();
		
	}
}

puzzledpublic 4년 전 0

본문 코드 테스트케이스 계속 돌려보다가 반례 찾아서 올려봅니다.

M이 시작된 위치를 알아야 풀 수 있었네요. 좀 노가다로 푼거 같음..

INPUT:
5
OMOLA
MOMMO
OOMOA
LAOLA

OUTPUT:
1

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

접근 방법 질문

puzzledpublic 4년 전 0

puzzledpublic 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말