글 읽기 - 카카오 코드 페스티벌 예선 2번, 보행자 천국 질문입니다

jaejin_me 5년 전 0

카카오 코드 페스티벌을 풀고 있는데요.

1번을 풀고 2번을 풀고있는데, 도중에 모르겠어서 간단하게 풀이가 설명된 카카오 글을 읽고 코드를 짰습니다.

풀이에서 제안하는 방식으로 풀이를 했는데 어디서 틀린걸까요?

테스트만 통과하고 제출하면 정답처리를 못받네요..

#include <vector>
#include <cstring>

using namespace std;

int MOD = 20170805;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int r[501][501]; //오른쪽으로 갈수있는 경우의 수
int b[501][501]; // 아래쪽으로 갈수있는 경우의 수
int solution(int m, int n, vector<vector<int>> city_map) {
    memset(r, 0, sizeof r);
    memset(b, 0, sizeof b);
    MOD = 20170805;
    r[1][1] = b[1][1] = 1;
    
    for(int i=1; i<=m;i++){   
        for(int j=1;j<=n;j++){
            if(city_map[i-1][j-1]==0){
                r[i][j] += (r[i][j-1] + b[i-1][j]);
                b[i][j] += (r[i][j-1] + b[i-1][j]);
            }
            else if(city_map[i-1][j-1]==1){
                r[i][j] = 0;
                b[i][j] = 0; 
            }
            else{
                r[i][j] = r[i][j-1];
                b[i][j] = b[i-1][j];                                
            }
        }
    }
    
    return r[m][n-1]%MOD+b[m-1][n]%MOD;
}

wondy1128 5년 전 1

아래와 같이 수정하면 맞습니다.

#include <vector>
#include <cstring>

using namespace std;

int MOD = 20170805;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int r[501][501]; //오른쪽으로 갈수있는 경우의 수
int b[501][501]; // 아래쪽으로 갈수있는 경우의 수
int solution(int m, int n, vector<vector<int>> city_map) {
    memset(r, 0, sizeof r);
    memset(b, 0, sizeof b);
    MOD = 20170805;
    r[1][1] = b[1][1] = 1;
    
    for(int i=1; i<=m;i++){   
        for(int j=1;j<=n;j++){
            if(city_map[i-1][j-1]==0){
                r[i][j] = (r[i][j] + r[i][j-1] + b[i-1][j])%MOD;
                b[i][j] = (b[i][j] + r[i][j-1] + b[i-1][j])%MOD;
            }
            else if(city_map[i-1][j-1]==1){
                r[i][j] = 0;
                b[i][j] = 0; 
            }
            else{
                r[i][j] = r[i][j-1];
                b[i][j] = b[i-1][j];                                
            }
        }
    }
    
    return (r[m][n-1]+b[m-1][n])%MOD;
}

exqt 5년 전 1

문제를 읽지는 않았지만 큰수를 다르는 문제에선 매번 % MOD 연산을 해주셔야 합니다. 그래야 오버플로우가 발생하지 않습니다.

r[i][j] += (r[i][j-1] + b[i-1][j]); 를 r[i][j] = (r[i][j] + r[i][j-1] + b[i-1][j]) % MOD; 이런식으루요

리턴값도 r[m][n-1]%MOD+b[m-1][n]%MOD; 로 하시면 둘다 MOD/2가 넘는값일때 답이 틀립니다.

(r[m][n-1]%MOD+b[m-1][n]%MOD) % MOD; 로 고쳐주세요.

jaejin_me 5년 전 1

왕.. 감사합니다

wondy1128, exqt님 최고!! bb!

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

문제

문제

출처

ICPC

카카오 코드 페스티벌 예선 2번, 보행자 천국 질문입니다

jaejin_me 5년 전 0

wondy1128 5년 전 1

exqt 5년 전 1

jaejin_me 5년 전 1

wondy1128, exqt님 최고!! bb!

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말