Tetromino

문제 복기

알고리즘

1. 먼저 어떤 도형을 놓을 것인지 결정한다. - 도형 별로 대칭, 회전했을 때 나오는 가능한 모든 경우의 수를 구한다. 그러면 총 19가지의 도형이 나오는 것을 알 수 있다. 각각의 도형에 대해 좌표를 구한다.

2. 어디에 놓을 것인지 결정한다. - 대략 N*M 가지 경웅의 수.

3. 전체 경우의 수 = 19*NM = 19*500*500 <<< O(1억=1초)

Tip : 공통되는 부분 합치기(계산 줄이기)

1. ㅗ 모양의 경우 ㅗ,ㅜ,ㅓ,ㅏ 4가지 모양이 나올 수 있는데 공통되는 ㅡ,ㅣ 부분을 temp2에 저장하고, i 또는 j의 범위에 따라 temp 합을 저장한다.

2. i,j 기준을 잡고, 범위체크를 해줄 때 범위 조건이 3개 이상나오게 된다면 기준을 다시 잡아서 조건이 2개를 넘지 않도록 적절히 수정해준다!

if (j+2 < m) {
    int temp = a[i][j] + a[i][j+1] + a[i][j+2];
    if (i-1 >= 0) {
        int temp2 = temp + a[i-1][j+1];
        if (ans < temp2) ans = temp2;
    }
    if (i+1 < n) {
        int temp2 = temp + a[i+1][j+1];
        if (ans < temp2) ans = temp2;
    }
}
if (i+2 < n) {
    int temp = a[i][j] + a[i+1][j] + a[i+2][j];
    if (j+1 < m) {
        int temp2 = temp + a[i+1][j+1];
        if (ans < temp2) ans = temp2;
    }
    if (j-1 >= 0) {
        int temp2 = temp + a[i+1][j-1];
        if (ans < temp2) ans = temp2;
    }
}

구현

최댓값을 갖는 합 찾기 구현 : 19가지 도형각각에 대해 NM 가지 위치에 각 놨을 때 최대합을 저장하고, 갱신해준다. 예를 들어 막대 모양에서 시작해 네모, 꽈배기, ..모양으로 진행될수록 다음과 같은 코드를 반복한다. 전체 문제의 해(ans)와 각각의 도형마다 각 위치에서 갖는 합을 temp라고 하면 ans에 temp를 더해가고, 각각의 도형에 대해 temp가 더 큰 값이 나와서 ans가 큰 값이 되면 ans를 더 큰 값으로 갱신한다!

if(ans<temp) ans = temp;//ans = 13, 여기서 만든 temp합은 15라면 ans는 temp가 된다!

//1.막대 2가지 
				if(j+3<m) {
					int temp = a[i][j] + a[i][j+1] + a[i][j+2] + a[i][j+3];
					if(ans<temp) ans = temp;//4
				}
				if(i+3<n) {
					int temp = a[i][j] + a[i+1][j] + a[i+2][j] + a[i+3][j];
					if(ans<temp) ans = temp;//5 :ans =4->5.
				}
				//2. 네모 1가지 
				if(i+1 < n && j+1<m) {
					int temp = a[i][j] + a[i][j+1] + a[i+1][j] + a[i+1][j+1];
					if(ans<temp) ans = temp;//ans = 9
				}
				//3.꽈배기 4가지 
				if(i-1>=0 && j+2<m) {
					int temp =  a[i][j] + a[i][j+1] + a[i-1][j+1] + a[i-1][j+2];
					if(ans<temp) ans = temp;//ans = 13
				}
				if(i+2<n && j+1<m) {
					int temp =  a[i][j] + a[i+1][j] + a[i+1][j+1] + a[i+2][j+1];
					if(ans<temp) ans = temp;//ans = 13, 여기서 만든 temp합은 15라면 ans는 temp가 된다!
				}