글 읽기 - 코드의 오류나 반례를 찾아주세요.

asd123 5년 전 0

각 line 별로 연결할수 있는 경우를 찾고, 상하에 대한 결과를 찾아 최소값을 구하는 방법으로 진행을 했는데요.

또한 N이 2이상인 경우, 왼쪽, 오른쪽, 대각선으로 shift한 결과를 모두 모아, 최소인 값을 출력하도록 구현했습니다.

이런 방식으로 코딩한 결과 50% 언저리에서 에러가 나는데요

잘못된 부분이나 반례를찾아주시면 감사하겠습니다.

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

#define MAX_VAL 1000000
int N, W;

int solve(int E[10005][2]) {
    int DP1[10005][2] = {0,}; //윗라인
    int DP2[10005][2] = {0,}; //아랫라인
    int DP[10005][2] = {0,}; //최종


    //윗라인 처리
    DP1[1][0] = 1;
    DP1[1][1] = MAX_VAL;
    for(int i = 2; i <= N; i++) {
        DP1[i][0] = 1 + min(DP1[i-1][0], DP1[i-1][1]);

        if(E[i][0] + E[i-1][0] <= W) // 이전거와 병합 가능한경우
            DP1[i][1] = DP1[i-1][0];
        else                         // 불가능한 경우 min 처리 못하게...
            DP1[i][1] = MAX_VAL;
        
    }

    //아랫라인 처리
    DP2[1][0] = 1;
    DP2[1][1] = MAX_VAL;
    for(int i = 2; i <= N; i++) {
        DP2[i][0] = 1 + min(DP2[i-1][0], DP2[i-1][1]);

        if(E[i][1] + E[i-1][1] <= W) // 이전거와 병합 가능한경우
            DP2[i][1] = DP2[i-1][0];
        else                         // 불가능한 경우 min 처리 못하게...
            DP2[i][1] = MAX_VAL;
        
    }

    //최종 처리
    //DP[][0] : 상하X
    //DP[][1] : 상하O
    
    DP[1][0] = 2;
    if(E[1][0] + E[1][1] <= W)
        DP[1][1] = 1;
    else   
        DP[1][1] = MAX_VAL;

    for(int i = 2; i <= N; i++) {
        DP[i][0] = 
            min(
                DP[i-1][1] + 2, //이전에 상하 + 현재 각각
                min(DP1[i][0], DP1[i][1]) + min(DP2[i][0], DP2[i][1])
            );
        if(E[i][0] + E[i][1] <= W) {
            DP[i][1] = min(DP[i - 1][0], DP[i-1][1]) + 1 ; //이전 최저값 + 1
        }
        else
            DP[i][1] = MAX_VAL;


    }

    return min(DP[N][0], DP[N][1]);
}
void shiftL(int arr[10005][2], int n) {
    for(int j = 0; j < 2; j++){
        int tmp = arr[1][j];
        for(int i = 1; i < n; i++)
            arr[i][j] = arr[i+1][j];
        arr[n][j] = tmp;
    }
}
void shiftL(int arr[10005][2], int n, int j) {
    int tmp = arr[1][j];
    for(int i = 1; i < n; i++)
        arr[i][j] = arr[i+1][j];
    arr[n][j] = tmp;
}

void shiftR(int arr[10005][2], int n) {
    for(int j = 0; j < 2; j++) {
        int tmp = arr[n][j];
        for(int i = n; i > 1; i--)
            arr[i][j] = arr[i-1][j];
        arr[1][j] = tmp;
    }
}
void shiftR(int arr[10005][2], int n, int j) {
    int tmp = arr[n][j];
    for(int i = n; i > 1; i--)
        arr[i][j] = arr[i-1][j];
    arr[1][j] = tmp;
}

int main() {
    cin.sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;
    while (T--) {
        cin >> N >> W;

        int E[10005][2] = {0,};
        
        // 기본형
        for(int i = 1; i <= N; i++) cin >> E[i][0];
        for(int i = 1; i <= N; i++) cin >> E[i][1];

        int r = solve(E);

        if(N > 1) {
            int E2[10005][2] = {0,};
            for(int i = 1; i <= N; i++) E2[i][0] = E[i][0];
            for(int i = 1; i <= N; i++) E2[i][1] = E[i][1];
            shiftL(E2, N);
            r = min(r, solve(E2));
            shiftR(E2, N);

            // for(int i = 1; i <= N; i++) E2[i][0] = E[i][0];
            // for(int i = 1; i <= N; i++) E2[i][1] = E[i][1];

            shiftR(E2, N);
            // for(int i = 1; i <= N; i++) cout << E2[i][0] << " "; cout << endl;
            // for(int i = 1; i <= N; i++) cout << E2[i][1] << " "; cout << endl;

            r = min(r, solve(E2));

            
            N+=2;
            for(int i = 2; i < N; i++) E2[i][0] = E[i-1][0];
            for(int i = 2; i < N; i++) E2[i][1] = E[i-1][1];
            
            E2[1][0] = E2[1][1] = W;
            E2[N][0] = E2[N][1] = W;

            // 역슬래시
            shiftL(E2, N, 0);
            r = min(r, solve(E2)-4);
            shiftR(E2, N, 0);

            // 슬래시

            shiftL(E2, N, 1);
            r = min(r, solve(E2)-4);

        }
        cout << r << endl;
    }
    return 0;
}

djm03178 5년 전 2

참고로 알려드리자면, 이 문제의 테스트 파일은 딱 1개이기 때문에 틀리면 무조건 50%에서 틀리게 됩니다. (100%라고 뜨는 게 보일 수 있을지도 모르겠습니다.)

srand 5년 전 0

1
6 9443
7422 2745 8376 2874 1159 7119
9400 5836 7028 6597 5881 7640

11 ( => 10 )

1 3 4 6 6 10
2 3 5 7 8 9

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

문제

문제

출처

ICPC

코드의 오류나 반례를 찾아주세요.

asd123 5년 전 0

djm03178 5년 전 2

srand 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말