글 읽기 - 17825 틀렸습니다.

kipper152 3년 전 1

Input:

3 5 2 5 3 5 2 1 3 1

Output:

246

위의 test case 답이 232로 잘못 나오길래 40번째 줄을 추가해줬습니다.

추가하고 다시 문제의 3번째 예제를 입력해보니 답이 잘못 나오더라구요..

그래서 일단 다시 주석처리를 했습니다. 하지만 어디서 틀린건지 전혀 모르겠네요.

또한 도착한 칸에 이미 다른 말이 존재하는 경우 말의 위치는 이동시키고 , 점수에는 포함시키지 않았는데

제가 제대로 이해한 게 맞나요?

도움 부탁드립니다.

=================================================================================================================================

수정했습니다.

제가 문제 조건을 잘못 이해했습니다.

움직였을 때, 해당 칸에 다른 말이 존재한다면
해당 조합은 아예 무효시키는 걸로 수정했더니 맞았습니다.

또한 40에서 다른 경로로 들어오는 경우를 생각을 못했습니다.

이 부분들을 수정했더니 맞았습니다.

아래는 제가 문제를 풀면서 참고한 test case들 입니다.

3 1 1 5 4 5 3 3 2 5

204

5 5 5 5 5 1 1 1 1 1

167

5 5 5 5 5 2 2 2 2 2

160

5 5 5 5 5 2 2 1 3 3

161

4 5 5 5 3 4 3 5 3 4

229

#include <iostream>
using namespace std;

int flag[4] ={0,};
int pos[4]={0,}; // position of horse
int mv[10]={0,};

int map[40]={0,};
int MAX =0;

bool move(int idx, int len)
{
    int start = pos[idx];
    int next = start;
    
    if(start > 40 ) return true;
    
    if(start ==10 || start ==20 || start ==30 || flag[idx])
    {
        if(start == 30 && flag[idx]==0){
            next = 28;
            len--;
        }
        
        flag[idx] = 1;

        for(int i=0;i<len;i++){
            if(next >= 40){
                next = 41;
                break;
            }
            next = map[next];
        }
    }
    else    next += 2 * len;
    
    
    for(int i=0;i<4;i++){
        if(pos[i] == next && next <= 40){
           // if(flag[i] == flag[idx]){
                pos[idx] = next;
                return false;
            //}
        }
    }
    
    pos[idx] = next;
    return true;
    
}


void DFS(int cnt , int sum)
{
    if(cnt == 10){
        if(MAX < sum)   MAX = sum;
        return ;
    }
    
    for(int i=0;i<4;i++){
        
        int tmp1 = pos[i];
        int tmp2 = flag[i];
        
        int res1 = move(i,mv[cnt]);
            
        int res = pos[i];
        
        if(res1 == false)    res = sum;
        else if(res > 40)   res = sum;
        else    res +=sum;
        
        DFS(cnt+1,res);
        
        pos[i] = tmp1;
        flag[i] = tmp2;
        
    }
}

int main(void)
{
    for(int i=0;i<10;i++)   cin >> mv[i];
    for(int i=0;i<3;i++)    map[10+3*i] = 10 + 3*(i+1);
    for(int i=0;i<2;i++)    map[20+2*i] = 20 + 2*(i+1);
    for(int i=0;i<3;i++)    map[28-i] = 28  - (i+1);
    for(int i=0;i<3;i++)    map[25+5*i] = 25 + 5*(i+1);

    map[24] =25;
    map[19] =25;
    
    DFS(0,0);

    cout << MAX;
    return 0;
}

kipper152 3년 전 1

수정한 코드입니다.

#include <iostream>

using namespace std;

int pos[4] = {0,};// 현재 말들의 위치
int blue[4] = {0,};//blue 영역에 들어갔는지 체크
int map[41]={0,};

int mv[10];
int MAX=0;


bool move(int len ,int idx)
{

    int start = pos[idx];
    int next = start;
    
    if(start ==10 || start ==20 || start == 30 || blue[idx]){
        
        if(start ==30 && blue[idx] ==0){
            next = 28;
            len--;
        }
        
        blue[idx]=1;
        for(int i=0;i<len;i++){
            if(next > 40 )  break;
            next = map[next];
        }
    }
    else    next = start + 2*len;
    
    
    for(int i=0;i<4;i++){
        if(pos[i] == next && next <= 40) {
            if( idx == i )  continue;
            if(blue[idx] == blue[i] || next == 40 ) return false;
        }
    }
    
    pos[idx] = next;
    return true;
}

void DFS(int cnt , int sum)
{
    if(cnt == 10){
        if(sum > MAX) {
            MAX = sum;
        }
        return;
    }
    
    for(int i=0;i<4;i++){
        
        if(pos[i] > 40  )   DFS(cnt+1 , sum);
        else{
            
            int idx = pos[i];
            int tmp = blue[i];

            bool res = move(mv[cnt],i);
            
            // 이미 해당 칸에 다른 말이 존재하는 경우 , 해당 조합은 무효화, 움직이지 않음
            if(res==0) {
                pos[i] = idx;
                blue[i] = tmp;
                continue;
            }
                        
            if(res && pos[i] > 40)  DFS(cnt+1 , sum);
            else if(res && pos[i]<= 40) DFS(cnt+1, sum+pos[i]);

            pos[i] = idx;
            blue[i] = tmp;

        }
    }
}

int main(void)
{
    for(int i=0;i<10;i++)   cin >> mv[i];

    for(int i=0;i<3;i++)    map[10+3*i] = 10+3*(i+1);
    for(int i=0;i<2;i++)    map[20+2*i] = 20+2*(i+1);
    for(int i=0;i<3;i++)    map[28-i] = 28-(i+1);
    for(int i=0;i<4;i++)    map[25+5*i] = 25+5*(i+1);

    map[24]=25;
    map[19]=25;
    
    DFS(0,0);
    
    cout << MAX;
    
    return 0;
}

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

문제

문제

출처

ICPC

17825 틀렸습니다.

kipper152 3년 전 1

kipper152 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말