모든 테스트 케이스랑 반례 찾아서 넣어도 맞게 나옵니다

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

2-F

작성

안녕하세요!

오랜만에 다시 코테를 푸는데 맞왜틀이 나와서 질문 드립니다!

#include <iostream>
using namespace std;

int N, M, J;
int l, r, cnt;

int main(){
    cin >> N >> M >> J;
    
    // 초기화
    l = 1; r = M; cnt = 0;
    
    for (int i = 0; i < J; i++){
        int apple;
        cin >> apple;

        // 범위 안이라서 움직일 필요 없다.
        if (apple >= l && apple <= r) continue;
        
        // 왼쪽에 가까우면 왼쪽으로 이동 오른쪽에 가까우면 오른쪽으로 이동
        int leftLength = abs(l - apple);
        int rightLength = abs(r - apple);
        bool isLeft = leftLength < rightLength ? true : false;

        if (isLeft){
            l -= leftLength;
            r -= leftLength;
            cnt += leftLength;
        }
        else{
            l += rightLength;
            r += rightLength;
            cnt += rightLength;
        }    
    }

    cout << cnt;

    return 0;
}

제가 만든 로직대로라면 절대로 경계값을 벗어날 수가 없습니다.
왜냐하면 문제에서 "각 사과는 N칸중 한 칸의 상단에서 떨어지기 시작하며" 라고 주어져 있기 때문입니다.

67%에서 틀렸다고 나옵니다..!

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 가인님 ㅎㅎ

코드를 보시면 거리를 기반으로 판단하게 되는데요. 만약 M이 1일 때 저 로직은 깨지게 됩니다.

isLeft 변수가 “어느 쪽으로 이동 거리가 더 짧은지”만 알려줄 뿐, 사과가 바구니의 왼쪽에 떨어졌는지 오른쪽에 떨어졌는지를 직접 알려주진 않습니다.

가인님 코드를 보시면

leftLength = abs(l - apple) 은 사과와 바구니 왼쪽 끝 사이의 거리
rightLength = abs(r - apple) 은 사과와 오른쪽 끝 사이의 거리

을 상징하고 두 값 중 작은 쪽이 “짧은 이동”이긴 하지만,

사과가 이미 바구니 범위 (l ≤ apple ≤ r) 안에 있다면 이동이 전혀 필요 없고,
사과가 바구니의 왼쪽 밖에(apple < l) 있으면 반드시 왼쪽으로 가야 하며,
사과가 오른쪽 밖에(apple > r) 있으면 반드시 오른쪽으로 가야 합니다.

따라서 만약 abs를 쓸거면 다음과 같이 써야 합니다.

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, J;
    cin >> N >> M >> J;

    int l = 1;
    int r = M;
    long long cnt = 0;

    for (int i = 0; i < J; i++) {
        int apple;
        cin >> apple;

        int leftLength  = abs(l - apple);
        int rightLength = abs(r - apple);
        bool isLeft     = leftLength < rightLength;

        if (apple < l || apple > r) {
            int diff = isLeft ? leftLength : rightLength;

            if (apple < l) {
                diff = leftLength;
                isLeft = true;
            } else if (apple > r) {
                diff = rightLength;
                isLeft = false;
            }

            cnt += diff;
            if (isLeft) {
                l -= diff;
                r -= diff;
            } else {
                l += diff;
                r += diff;
            }
        }
    }

    cout << cnt;
    return 0;
}

후... 여러번 고민하다 알아냈네요 ㅎㅎ

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

요가인

질문자

아.. 첫번째 테스트 케이스가 운좋게 값이 맞아서 통과했던 거네요..
감사합니다
저도 한참 찾았는데 뭐가 문젠지 몰랐는데 이해했습니다~!

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

모든 테스트 케이스랑 반례 찾아서 넣어도 맞게 나옵니다