💁♀️ DP 사용!
Troubleshooting
import java.io.IOException;
import java.util.Scanner;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static char[][] lcs;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
lcs = new char[n][m];
for(int i=0; i<n; i++) {
lcs[i] = br.readLine().toCharArray(); //이렇게해도 들어가네
}
int len = dp(n,m);
System.out.print(len*len);
}
public static int dp(int n, int m) {
int len = 1;
boolean isOneExistence = false;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
char lenChar = (char)(len +'0');
if(lcs[i][j] == lenChar) {
isOneExistence = true;
if(i >0 && j>0) {
if(lcs[i-1][j] == lenChar&& lcs[i][j-1] ==lenChar && lcs[i-1][j-1] ==lenChar) {
len++;
lcs[i][j] = (char)(len + '0');
}
if((lcs[i-1][j] != '0' && lcs[i][j-1] != '0' && lcs[i-1][j-1] != '0') && (lcs[i-1][j] != lcs[i][j-1])) {
lcs[i][j] = lcs[i-1][j] > lcs[i][j-1] ? lcs[i-1][j] : lcs[i][j-1];
}
}
}
}
}
if(!isOneExistence)len = 0;
return len;
}
}문제
틀렸습니다를 받았다.
원인
반례를 발견했다.
4 4
1111
1111
1111
1111
#answer
16
# myOutput
4dp의 이중for문 속 첫번째 조건문 조건이 잘못됐었다.
1일때에 실행할 수 있도록 아래와같이 조건문을 짰었는데,
if(lcs[i][j] == lenChar)
생각해보니 숫자가 업데이트되므로 2,3...의 수가될수도있다.
해결
if(lcs[i][j] != '0')로 수정했다.
Troubleshooting 2
문제
틀렸습니다를 받았다.
원인
6 6
111000
111111
111110
111110
011110
010000
#answer
16
# myOutput
25예외 케이스를 발견했다.
한 변의 길이를 누적하는 lcs배열의 결과를 보니, 이 문제는 가운데 정사각형이 정답이 되어야하는데 첫줄부터 계속 누적되는것이 문제였다.
111000
122111 //여기부터 새로 1부터 누적되게 어떻게해야할까..
123330
123440
013450
010000맨 뒤에서부터 누적되되록해도 똑같을거다..
내 로직으로 풀면, 안되는부분을 발견했다.
lcs의 i,j를 오른쪽 아래 꼭짓점으로 하는 가장 큰 정사각형 변의 길이인데, 이렇게하면 예를들어
1111
1111
1111
1111
위와 같은 케이스가 있을 때, 3행 2열에서 문제가 생긴다.
1111
1222
13...
이렇게 3이 아닌 2가 되어야하는데, 벌써부터 3으로 바뀌어버린다.
해결
기준 자리의 왼쪽, 위, 왼쪽위방향 대각선의 수가 모두 같을때, 다를 때 등 복잡하게 조건 가져갈필요없이,
위, 왼쪽, 왼쪽상단방향의 대각선에 있는 값 중 가장 작은 값에 1을 더한값으로 변경하면된다.
Troubleshooting 3
package dp;
import java.io.IOException;
import java.util.Scanner;
public class makeOne {
public static void main(String[] args) throws IOException {
long[][] D = new long[1001][1001];
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
long max = 0;
for(int i=0; i<n ;i++) {
String mline = sc.next();
for(int j=0; j<m; j++) {
D[i][j] = Long.parseLong(String.valueOf(mline.charAt(j)));
}
}
max = dp(n,m, D);
System.out.println(max*max);
}
public static long dp(int n, int m, long[][] D) {
long max = 1;
boolean isOneExistence = false;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(D[i][j] != 0) {
isOneExistence = true;
if(i >0 && j>0) {
if(D[i-1][j] != 0 && D[i][j-1] != 0 && D[i-1][j-1] != 0) {
if(D[i-1][j] == D[i][j-1] && D[i-1][j] == D[i-1][j-1] && D[i][j-1] == D[i-1][j-1]) {
D[i][j] = ++max;
continue;
}
D[i][j] = Math.min(D[i-1][j-1] , Math.min(D[i-1][j],D[i][j-1])) + 1;
}
}
}
}
}
if(!isOneExistence)max = 0;
return max;
}
}문제
틀렸습니다를 받았다.
원인
if(D[i-1][j] == D[i][j-1] && D[i-1][j] == D[i-1][j-1] && D[i][j-1] == D[i-1][j-1]) {
D[i][j] = ++max;
continue;
} 이 코드처럼 max값을 누적하며 채우면, 또 다른 정사각형이 만들어질 때 누적된 값이 들어가서 잘못된 값이 들어가게된다.
예를 들어보자
11011
11011위와같은 상황이 있을 때 한 변의 최대값은 2이다.
그러나 해당코드로 진행하면
11011
12013이렇게돼서 3이 최대값이 되어버린다.
해결
D[i][j] = Math.min(D[i-1][j-1] , Math.min(D[i-1][j],D[i][j-1])) + 1;
if(max < D[i][j]) {
max = D[i][j];
}위,왼쪽, 왼쪽 상단방향의 대각선 세 개의 값이 같은지 다른지에 따라 나누지않고 무조건 '세 값중 최솟값 +1'의 풀이로 진행하며, 대신 값을 채울때마다 max값을 업데이트해주는 식으로 수정한다.
제출코드
import java.io.IOException;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws IOException {
long[][] D = new long[1001][1001];
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
long max = 0;
for(int i=0; i<n ;i++) {
String mline = sc.next();
for(int j=0; j<m; j++) {
D[i][j] = Long.parseLong(String.valueOf(mline.charAt(j)));
if(D[i][j] == 1 && j>0 && i>0) {
D[i][j] = Math.min(D[i-1][j-1] , Math.min(D[i-1][j],D[i][j-1])) + 1;
}
if(max < D[i][j]) {
max = D[i][j];
}
}
}
System.out.println(max*max);
}
}공부한 사항
- toCharArray()를 이용해서 char배열로 받아 이차원배열의 한 행으로 바로 넣을 수 있다.
char[][] lcs = new char[3];
lcs[0] = br.readLine().toCharArray(); -
3개의 원소에서 최솟값을 구할 때에는 Math.min()안에 파라미터로 또 Math.min()을 이용할 수 있다.
Math.min(D[i-1][j-1] , Math.min(D[i-1][j],D[i][j-1])) -
String.valueOf()에는 어떤값이든 넣을 수 있다. (char타입도 가능하다)
