글 읽기 - 1021 반례 부탁드립니다..

hacastle 3년 전 0

deque에 수를 넣은 상태에서

왼쪽, 오른쪽 중 빠른 경로를 판단하여

pop, push 과정을 반복했습니다.

예제케이스와 게시판 케이스는 다 통과하는데 제가 어떤 점을 간과하고 있는지 궁금합니다.

반례가 존재한다면 알려주시면 감사하겠습니다.

#include<stdio.h>
#include<iostream>
#include<deque>
using namespace std;
deque<int> dq; 
int arr[51];
int fall[51]; // pop된 숫자 체크
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) cin >> arr[i];
    
    for (int i = 1; i <= n; i++) {
        dq.push_back(i);
        fall[i] = 1;
    }
    
    int answer = 0;
    for (int i = 0; i < m; i++)
    {
        int range = arr[i];
        int num = 0;
        if (dq.front() > arr[i]) range += n;

        for (int j = dq.front(); j <= range; j++) {
            if (j > n) if (fall[j - n] == 1) num += 1;
            if (fall[j] == 1) num += 1;
        }
        if (num <= (int)(dq.size() / 2) + 1) { // 왼쪽이 더 빠를 때
            for (int j = 1; j < num; j++) {
                dq.push_back(dq.front());
                dq.pop_front();
                answer += 1;
            }
        }
        else { //오른 쪽이 더 빠를 때
            for (int j = 1; j <= dq.size() - num + 1; j++) {
                dq.push_front(dq.back());
                dq.pop_back();
                answer += 1;
            }
        }
        fall[dq.front()] = 0; //pop할 숫자를 맨앞으로 옮긴 후, 그 이후 과정.
        dq.pop_front();

    }
    cout << answer;
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1021 반례 부탁드립니다..

hacastle 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말