글 읽기 - 왜 틀린거죠..?

playsworld16 2년 전 0

스프라그-그런디 정리를 이용한 평범한 문제라고 생각했는데

왜 틀렸는지 모르겠습니다

#include <bits/stdc++.h>
using namespace std;

int n;
int A[201];

int g[201][201];
int ans[201][201];
int solve(int l, int r){
    
    if (g[l][r] != -1) return g[l][r];
    if (l >= r) return g[l][r] = 0;
    
    ans[l][r] = -1;
    vector<int> cnt(300);
    for(int i = l; i < r; i++){
        if (i + A[i] <= r) {
            int tx = solve(l, i-1)^solve(i+A[i]+1, r);
            cnt[tx]++;
            if (tx == 0 && ans[l][r] == -1) ans[l][r] = i;
        }
    }
    
    int x = 0;
    while(cnt[x]) x++;
    return g[l][r] = x;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> A[i];
    
    memset(g, -1, sizeof(g));
    memset(ans, -1, sizeof(ans));
    
    solve(1, n);
    cout << ans[1][n];
}

sait2000 2년 전 1

solve(i+A[i]+1, r)가 i+A[i]+1에 201이 들어갈 수 있습니다. 그러면 범위를 넘습니다.

http://boj.kr/1d3b597ea4ee4145a9d8971fe4aa0f88

playsworld16 2년 전 0

생각지도 못한 부분이었네요.. 하나 배워갑니다. 정말 감사합니다.

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

문제

문제

출처

ICPC

왜 틀린거죠..?

playsworld16 2년 전 0

sait2000 2년 전 1

playsworld16 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말