글 읽기 - 반례를 찾아주십시오...

sus1226 4년 전 0

같은 문제인 보드 문제는 풀었는데 이 문제는 58%에서 틀렸다고 나오네요. 이유가 궁금합니다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <vector>
#include <cmath>

using namespace std;

int map[100][100] = { 0 };
string DP[100][100];
int N;

int dx[2] = {1, 0};
int dy[2] = {0, 1};

string Plus(string a, string b)
{
    if(a == "") return b;
    else
    {
        if(a.length() < b.length())
        {
            string c = a;
            a = b;
            b = c;
        }
        if(a.length() > b.length())
        {
            int temp = 0;
            for(int i = 0; i < b.length(); i++)
            {
                if((int)a[a.length() - i - 1] + (int)b[b.length() - i - 1] - 2 * '0' + temp >= 10)
                {
                    a[a.length() - i - 1] = (char)((int)a[a.length() - i - 1] + (int)b[b.length() - i - 1] - '0' - 10 + temp);
                    temp = 1;
                }
                else
                {
                    a[a.length() - i - 1] = (char)((int)a[a.length() - i - 1] + (int)b[b.length() - i - 1] - '0' + temp);
                    temp = 0;
                }
            }
            int x = b.length();
            while(temp == 1)
            {
                if((int)a.length() - 1 - x < 0) { a = "1" + a; temp = 0; }
                else if((int)a[a.length() - 1 - x] - '0' + temp >= 10)
                {
                    a[a.length() - 1 - x] = (char)((int)a[a.length() - 1 - x] + temp - 10);
                    x++;
                }
                else
                {
                    a[a.length() - 1 - x] = (char)((int)a[a.length() - 1 - x] + temp);
                    temp = 0;
                }
            }
            return a;
        }
        else
        {
            int temp = 0;
            for(int i = 0; i < b.length(); i++)
            {
                if((int)a[a.length() - i - 1] + (int)b[b.length() - i - 1] - 2 * '0' + temp >= 10)
                {
                    a[a.length() - i - 1] = (char)((int)a[a.length() - i - 1] + (int)b[b.length() - i - 1] - '0' - 10 + temp);
                    temp = 1;
                }
                else
                {
                    a[a.length() - i - 1] = (char)((int)a[a.length() - i - 1] + (int)b[b.length() - i - 1] - '0' + temp);
                    temp = 0;
                }
            }
            if(temp == 1) return "1" + a;
            else return a;
        }
    }
}

void Jump()
{
    for(int i = 0; i < 2 * N - 2; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            if(i - j >= 0 && i - j < N && j >= 0 && j < N)
            {
                if(DP[i - j][j].size() != 0)
                {
                    for(int k = 0; k < 2; k++)
                    {
                        int x = i - j + dx[k] * map[i - j][j];
                        int y = j + dy[k] * map[i - j][j];
                        if(x >= 0 && x < N && y >= 0 && y < N) DP[x][y] = Plus(DP[x][y], DP[i - j][j]);
                    }
                }
            }
        }
    }
    cout << DP[N - 1][N - 1];
}

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

    cin >> N;
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++) cin >> map[i][j];
    }
    DP[0][0] = "1";
    Jump();
}

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

문제

문제

출처

ICPC

반례를 찾아주십시오...

sus1226 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말