글 읽기 - 재귀로 풀었는데 문제가 뭘까요..?

taehoon_gwon 6년 전 0

저는 재귀로 풀었어요. 3가지 규칙을 둬서

1. 오른쪽만 버릴 수 있으면 오른쪽만 버리기

2. 왼쪽의 최고값 이상인 오른쪽값이 나올땐 둘다 버리기

3. 1,2 해당 되지않으면 왼쪽만 버리기

이렇게 나오니 답은 다 나오던데 어떤 부분에서 틀린지 알수 있을까요..?

#include <iostream>
#include <vector>
using namespace std;
vector<int>leftDummy,rightDummy;
int n,maxLeft;
int maxScore;
void checkScore(vector<int>leftPack,vector<int>rightPack,int score){
    //두 더미 중 하나만 비더라도 종료
    if(leftPack.size()==0 || rightPack.size()==0){
        maxScore=score;
        return;
    }
    
    int topLeft = leftPack.front();
    int topRight = rightPack.front();
    
    //오른쪽이 왼쪽보다 작을 경우
    if(topRight<topLeft){
        score+=topRight;
        rightPack.erase(rightPack.begin());
        checkScore(leftPack, rightPack, score);
    }
    
    //오른쪽값이 왼쪽의 최고값보다 크거나 같을 경우 둘다 버리기
    else if(topRight>=maxLeft){
        leftPack.erase(leftPack.begin());
        rightPack.erase(rightPack.begin());
        checkScore(leftPack, rightPack, score);
    }
    
    //두 경우 아나리면 왼쪽만 버리기
    else{
        leftPack.erase(leftPack.begin());
        checkScore(leftPack, rightPack, score);
    }
}

int main(){
    cin>>n;
    int l,r;
    for(int i=0;i<n;i++) {
        cin>>l;
        leftDummy.push_back(l);
        if(l>maxLeft){
            maxLeft=l;
        }
    }
    for(int i=0;i<n;i++) {
        cin>>r;
        rightDummy.push_back(r);
    }
    checkScore(leftDummy, rightDummy, 0);
    printf("%d\n",maxScore);
}

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

문제

문제

출처

ICPC

재귀로 풀었는데 문제가 뭘까요..?

taehoon_gwon 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말