3-I 질문 있습니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

3-I

해결된 질문

작성

343

저는 visited 배열을 하나만 만들어서 풀려고 했습니다.

수빈이가 갈수있는 최소시간을 적은 map을 만든다 .(visited)
동생이 time 시간에 도달하는 좌표와 map을 비교한다.
동생의 좌표에 수빈이가 처음 도착한 시간이 time보다 작거나 같고 둘의 홀짝 정보가 같으면 time을 반환하고 아니면 다음 칸으로 넘어간다.

이렇게 풀었는데 9%에서 오답이 나옵니다. 꼭 배열을 두개 만들어야 하나요?

배열을 두개 만드는 것은 홀짝 정보를 대조하기 위함이라고 판단했고, 저는 수빈이의 최소시간과 동생이 이동한 시간을 비교하는 식을 썼습니다. 이 방법이 잘못되었다면 그 이유는 무엇이고 방법은 맞는데 틀린거라면 어느 부분이 잘못 되었는지 알 수 있을까요 ?

#include <bits/stdc++.h>
#define MAX 500001
using namespace std;
int visited[MAX];
int main() {
    int n, k;
    cin >> n >> k;
    queue<int> q;
    q.push(n);
    visited[n] = 1;

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        int _nx[] = {x + 1, x - 1, 2 * x};
        for (int i = 0; i < 3; i++) {
            int nx = _nx[i];
            if (nx < 0 || nx > 500000 || visited[nx]) continue;
            q.push(nx);
            visited[nx] = visited[x] + 1;
        }
    }
    int time = 1;
    while (1) {
        int bro = k + time * (time - 1) / 2;
        if (bro >= MAX) break;
        int myTime = visited[bro];
        if (myTime <= time && !(time & 1 ^ myTime & 1)) {
            cout << time - 1;
            return 0;
        }
        time++;
    }
    cout << -1;
    return 0;
}

C++코테 준비 같이 해요!

답변 2

큰돌

지식공유자

아 좀 더 정확히 말씀드리면 저 코드 뿐만 아니라 2차원배열 + 가면서 확인을 하는 로직이 없어서 틀린겁니다.

큰돌

지식공유자

하... 제가 굉장히 장문으로 답변을 남겼는데 날라가서.

다시 작성하니 저의 슬픔을 공감해주시길 ㅠ

흑.. 무튼 답변 드리자면 다음과 같습니다.

이렇게 풀었는데 9%에서 오답이 나옵니다. 꼭 배열을 두개 만들어야 하나요?

> 2개가 아니라 2차원 배열입니다. 여기서 수빈이의 위치 정보와 동생의 위치 정보 두가지를 동시에 나타내는 2차원 배열이 필요합니다.

이 문제를 가장 쉽게 푸는 방법은 수빈이와 동생의 위치 정보가 담긴 50만 * 50만의 visited 배열을 만드는 것이죠. 그러나 이러한 배열을 만들면 시간초과가 나기 때문에 그렇게 하지 못하고

가면서 확인 + 홀짝 * 동생의 위치 배열로 이 문제를 푸는 것입니다.

배열을 두개 만드는 것은 홀짝 정보를 대조하기 위함이라고 판단했고

>> 왜 홀짝 정보를 비교할 거라 생각했나요? 코드를 보면 해당 부분을 이해한 것같아 설명을 생략하려다 다시 말씀 드리면 다음과 같습니다.

수빈이가 3초에 도착을 했고. 동생이 5초에 해당 위치에 도착을 하면. 수빈이는 그 위치에 5초만에 갈 수 있겠죠? 그러나 수빈이가 4초에 도착을 했다면 못 갈겁니다. 왜냐면 수빈이가 +1 또는 -1이 가능해서 왔다리~ 갔다리~ 하면서 3, 5, 7초에 해당위치로 갈 수 있지만.

4초에 만약 도착하면 4, 6, 8밖에 안되거든요. 즉, 짝수로 도착하면 짝짝, 홀수로 도착하면 홀홀밖에 불가능합니다.

따라서 해당부분에 해당하는 배열을 만들어 2차원 배열로 만들어야 합니다.

저는 수빈이의 최소시간과 동생이 이동한 시간을 비교하는 식을 썼습니다. 이 방법이 잘못되었다면 그 이유는 무엇이고 방법은 맞는데 틀린거라면 어느 부분이 잘못 되었는지 알 수 있을까요 ?

I님의 코드는 상당히 아름답습니다. 비트연산자. &의 올바른 이해. 짝홀간의 ^연산자. 그리고 time을 계산하는 부분에서 등차수열의 합을 이용하는 모습.

but, 해당 부분이 잘못되었습니다.

if (nx < 0 || nx > 500000 || visited[nx]) continue;

바로 이부분이죠.

왜 그럴까요?

예를 들어 수빈이가 1, 2, 4라는 경로로 4라는 경로에 2초만에 도착했다고 해봅시다.

하지만 이러한 경우의 수가 또 있죠. 1, 2, 3, 4 즉, 4라는 경로에 3초만에 도착하는 경우가 생길 수 있습니다. 이 때 2초만에 도착한 경우의 수만을 가지고 있는 visited라는 안타까운 녀석은 3초만에 도착하는 경우의 수를 "생각할 수 없습"니다.

그래서 틀린 겁니다.

하지만 굉장히 코드는 훌륭합니다.

감사합니다.

강사 큰돌 올림.

lll

질문자

하지만 이러한 경우의 수가 또 있죠. 1, 2, 3, 4 즉, 4라는 경로에 3초만에 도착하는 경우가 생길 수 있습니다. 이 때 2초만에 도착한 경우의 수만을 가지고 있는 visited라는 안타까운 녀석은 3초만에 도착하는 경우의 수를 "생각할 수 없습"니다.

이런 경우가 있군요...! 감사합니다 해결했습니다~

인프런 커뮤니티 질문&답변

3-I 질문 있습니다.