3-O 질문 있습니다.

Question

강의에서 나오는 풀이와 몇가지 차이가 있긴 하지만

- 인덱스를 100*H +N으로 구한다는 점

- 사다리를 12로 놓는다는 점

이 차이가 있는것 같다고 생각했습니다.

강사님 풀이 중 다음 부분에서 궁금한 점이 있습니다. H를 사다리라고 한다면

Hㅁㅁㅁㅁㅁ 를 탐색하고 난 이후에 for (int j = 1; j <= n; j++)부분으로 인해서 첫번째 공간에 사다리를 또 놓게되는 중복이 발생하지는 않는지 궁금합니다.

예를들어 처음에 Hㅁㅁ 인상태로 go를 하면 HㅁH를 탐색하고 첫번째 인덱스를 0으로 바꾼후

ㅁHㅁ 탐색 그 이후

ㅁㅁH 케이스에서 다시 HㅁH 가 발생하지 않는지 궁금합니다.

또한 저의 풀이는 계속 9%에서 시간초과가 발생하는데 그 이유가 궁금합니다.

for (int i = here; i <= h; i++) {
    for (int j = 1; j <= n; j++) {
        if (visited[i][j] || visited[i][j - 1] || visited[i][j + 1]) continue;
        visited[i][j] = 1;
        go(i, cnt + 1);
        visited[i][j] = 0;
    }
}

#include <bits/stdc++.h>
using namespace std;
int N, M, H;
int arr[34][12];
int res = 5;
bool simul() {
    for (int i = 1; i <= N; i++) {
        int depth = 0;
        int idx = i;
        while (depth <= H) {
            int point = arr[depth][idx];
            if (point == 1)
                idx++;
            else if (point == 2)
                idx--;
            depth++;
        }
        if (idx != i) return false;
    }
    return true;
}
void dfs(int hn, int level) {
    if (level >= res || level > 3) return;
    cout << hn << endl;
    int h = hn / 100;
    int n = hn % 100;
    if (hn == H * 100 + N) {
        if (simul()) {
            res = min(level, res);
        }
        return;
    }
    int nh = n < N ? h : h + 1;
    int nn = n < N ? n + 1 : 1;

    dfs(nh * 100 + nn, level);
    if (n < N && !arr[h][n] && !arr[h][n + 1]) {
        arr[h][n] = 1, arr[h][n + 1] = 2;
        dfs(nh * 100 + nn, level + 1);
        arr[h][n] = 0, arr[h][n + 1] = 0;
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> M >> H;
    for (int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        arr[x][y] = 1;
        arr[x][y + 1] = 2;
    }
    dfs(101, 0);
    if (res == 5)
        cout << -1;
    else
        cout << res;
    return 0;
}

Answer

lll님 안녕하세요. ㅎㅎ

좋은 풀이입니다. 나중에 색종이붙이기 문제를 푸시는데 그 코드와 유사합니다. y와 x를 * 1000을 통해서 인덱스를 잡고 들어가며 순차적으로 x, 다 전진 이후 y 이렇게 드가는 코드. 훌륭합니다.

일단 lll님의 코드 중 로직상 틀린점은 없는 것같습니다.

simul함수 : ok

dfs : ok

그렇다면 혹시나. 중복적인 함수호출은 많이 하는 것이 아닌가? 그 또한 아닙니다.

혹시나 운좋게 예제코드를 맞은 것은 아닌가? 사다리 잘 지었는지 확인해봤는데 그 또한 아닙니다.

but, 그러면 이 코드에서 어떻게 하면 시간초과를 해결할 수 있을까?

함수호출을 줄입니다. : http://boj.kr/c59a3833193041fa90a52167c5900eff

- 이렇게 해결하시면 됩니다.

[문의 답변]

Hㅁㅁㅁㅁㅁ 를 탐색하고 난 이후에 for (int j = 1; j <= n; j++)부분으로 인해서 첫번째 공간에 사다리를 또 놓게되는 중복이 발생하지는 않는지 궁금합니다.

>> 네 중복발생합니다.

>> but, 이 문제의 경우 n의 크기가 작아서 그닥 영향은 끼치지 않아요. 또한 continue가 있어서 함수호출부분에 있어서 중복적인 함수호출이 발생하지 않습니다.

감사합니다.

강사 큰돌 올림.

Answer

우와 ... 이거때문에 진짜 고생하고있었는데 답변해주셔서 감사합ㄴ니다 ㅜㅜㅜ

if (n < N && !arr[h][n] && !arr[h][n + 1] && level < 3) {

level < 3 조건만 추가 하니까 아슬아슬 통과하네요 ..! 3넘어가면 바로 return 해서 차이가 없을 줄 알았는데 ... 덕분에 하나더 배워갑니다...!

매번 질문 받아주셔서 감사해용

lll

3-O 질문 있습니다.

이 글과 비슷한 Q&A

단순대입 오류 발생 이유

간단한 질문이 있습니다.

문제로 해결하는 시간복잡도 4번 질문이 있습니다.

sort() 함수의 매개변수 cmp 함수가 동작하는 원리가 궁금합니다