글 읽기 - 33%에서 막히는데 반례가 있을까요

seokgukim 2년 전 0

일단 amho에 문자열로 저장한 입력을 뒤에서부터 하나씩 처리하며 제곱수인지 판별하고, 각 지점마다 가능한 합의 최소값을 찾도록 재귀하게 했는데

예외라고 생각한 것들 넣어봐도 맞는데 33%에서 막히네요.

반례가 혹시 있을까요?

#include <iostream>
#include <math.h>
#define INF 1000000000
using namespace std;

string amho;
int len;
long long dap[100001];//
bool issquare(long long num) {//빠른 제곱수 판별 함수
    long long temp;
    switch (num & 0x0f) {
    case 0:
    case 1:
    case 4:
    case 9:
        temp = (long long)(sqrt((double)num) + 0.5);
        return temp * temp == num;

    default:
        return false;
    }
}

long long decoder(int idx) {//해독기
    if (idx == 0) return 1;//0지점까지 호출에 성공한다면 1을 반환
    if (dap[idx]) return dap[idx];//이미 있는 값이면 반환
    int nidx = idx;//새 인덱스, 문자열 끝에서부터 시작
    long long mtp = 1;//배수 
    long long a = 0;//판별할 수
    while (nidx--) {//인덱스 0에 도달할 때까지
        int b = amho[nidx] - 48;//암호의 끝자리를 받아온다. char형이므로 -48을 해서 정수로 바꿈
        a += b * mtp;//a에 배수를 곱해 더해줌
        if (a > INF) break;//최대 범위를 넘으면 중단
        mtp *= 10;//배수를 배가
        if (issquare(a) && b) {//a가 제곱수고 b가 0이 아닌 경우
            if (dap[nidx] || decoder(nidx)) {//이전까지의 합이 있거나 재귀호출 값이 0이 아니면
                if (dap[idx]) dap[idx] = min(dap[idx], a + dap[nidx]);//이미 합이 있으면 최소값으로 갱신
                else dap[idx] = a + dap[nidx];//아니면 새 값을 넣어줌
            }
        }
    }
    return dap[idx];//합을 리턴
}

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

    cin >> amho;
    len = amho.length();
    long long aa = decoder(len);
    if (!aa) aa = -1;
    cout << aa;
}

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

문제

문제

출처

ICPC

33%에서 막히는데 반례가 있을까요

seokgukim 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말