17075번 유물 복원

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

왜 0ms인지 질문 : https://www.acmicpc.net/board/view/48091

dp 메모이제이션 캐시 cache 복습 코테 필수 추천 냅색 boj 백준

2019 연세대학교 컴퓨터과학과 프로그래밍 경진대회 D번

한 점에 대해서 모든 경우의 수들을 탐색.

t 2차원 배열은 -1인 곳에서 얼마만큼 사용을 했는지 "사용 횟수"로 접근했었다.

그러나 시간이 900ms가 넘었다.

정답자 분들 중 코드를 참고하였더니, 공식같은 것이 있었다.

사실 공식은 아니지만 조금만 더 생각해보면 접근할 수 있었던 식이다.

나는 그냥 아무 생각없이 for문 돌리면 되겠다 싶어 다른 방법은 생각하지 않았다.

해당 좌표(i, j)를 포함하는 나올 수 있는 모든 직사각형의 호출 횟수는 가로의 길이 = C, 세로의 길이 = R이라고 할 때,

(i + 1) * (j + 1) * (R - i) * (C - j)

이다.

시간이 무려 900ms가 넘는 코드

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 52
 
int R, C, K, m[Max][Max], t[Max][Max], sum;
bool use[Max][Max];
 
// (sr, sc) ~ (er, ec) '1'인 곳의 합
int calc(int sr, int sc, int er, int ec)
{
    int ret = 0;
 
    for (int i = sr; i <= er; i++) {
        for (int j = sc; j <= ec; j++) {
            if (m[i][j] == -1) {
                ++t[i][j]; // -1은 따로 t 2차원 배열에 그 횟수를 1 증가시킨다.
            }
            else {
                ret += m[i][j];
            }
        }
    }
 
    return ret;
}
 
// 한 점(r, c)을 기준으로 그 점에 대해서 모든 직사각형 안에 있는 1의 합을 구한다.
int simulation(int r, int c)
{
    int ret = 0;
 
    for (int i = r; i < R; i++) {
        for (int j = c; j < C; j++) {
            ret += calc(r, c, i, j);
        }
    }
 
    return ret;
}
 
// 정답 출력(K의 배수인지 검사)
void chk(int s)
{
    if ((sum + s) % K == 0) {
        printf("1\n");
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (m[i][j] == -1) {
                    printf("%d ", use[i][j] ? 1 : 0);
                }
                else {
                    printf("%d ", m[i][j]);
                }
            }
            printf("\n");
        }
        exit(0);
    }
}
 
// 백트래킹
void dfs(int r, int c, int s)
{    
    // K의 배수가 되는지 검사
    chk(s);
 
    if (c == C) {
        c = 0;
        ++r;
    }
 
    if (r == R) {
        return;
    }
 
    if (m[r][c] == -1) {
        use[r][c] = true;
        dfs(r, c + 1, s + t[r][c]);
        use[r][c] = false;
    }
 
    // 해당 칸(r, c)을 선택(덧셈)을 안 할 때
    dfs(r, c + 1, s);
}
 
int main()
{
    cin.tie(0);
 
    scanf("%d %d %d", &R, &C, &K);
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            scanf("%d", &m[i][j]);
        }
    }
 
    // 나올 수 있는 모든 직사각형에서 1의 합(단, -1인 곳은 t 배열에 그 횟수를 저장하였음)
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            sum += simulation(i, j);
        }
    }
 
    // 백트래킹
    dfs(0, 0, 0);
 
    printf("-1\n");
 
    return 0;
}

0ms 코드

#include <bits/stdc++.h>
 
using namespace std;
 
#define Max 52
 
int R, C, K, m[Max][Max], t[Max][Max], sum;
bool use[Max][Max];
 
// 정답 출력(K의 배수인지 검사)
void chk(int s)
{
    if ((sum + s) % K == 0) {
 
        printf("1\n");
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (m[i][j] == -1) {
                    printf("%d ", use[i][j] ? 1 : 0);
                }
                else {
                    printf("%d ", m[i][j]);
                }
            }
            printf("\n");
        }
 
        exit(0); // 바로 종료
    }
}
 
// 백트래킹
void dfs(int r, int c, int s)
{    
    // K의 배수가 되는지 검사
    chk(s);
 
    if (c == C) {
        c = 0;
        ++r;
    }
 
    if (r == R) {
        return;
    }
 
    if (m[r][c] == -1 && !use[r][c]) {
        use[r][c] = true;
        dfs(r, c + 1, s + t[r][c]);
        use[r][c] = false;
    }
 
    // 해당 칸(r, c)을 선택(덧셈) 안 할 때
    dfs(r, c + 1, s);
}
 
int main()
{
    cin.tie(0);
 
    scanf("%d %d %d", &R, &C, &K);
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            scanf("%d", &m[i][j]);
            if (m[i][j] == 1) {
                sum += (i + 1)*(R - i)*(j + 1)*(C - j); // 공식
            }
            else if (m[i][j] == -1) {
                t[i][j] += (i + 1)*(R - i)*(j + 1)*(C - j); // 공식
            }
        }
    }
 
    // 백트래킹
    dfs(0, 0, 0);
 
    printf("-1\n");
 
    return 0;
}