글 읽기 - 파라매트릭 서치

gshs340507 5년 전 0

파라매트릭 서치로 풀려 했는데 어디가 틀린걸까요..

반례가 있나요?

#include <bits/stdc++.h>
#define MAX 1000000

using namespace std;

int decom(int x);

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num;
    cin >> num;
    int ans = MAX;
    int L = 0, R = MAX;
    while(L <= R){
        int mid = (L + R) / 2;
        int res = decom(mid);
        if(res == num && mid < ans) ans = mid;
        if(res >= num) R = mid - 1;
        else L = mid + 1;
    }
    if(ans == MAX) cout << 0;
    else cout << ans;
}

int decom(int x)
{
    int res = x;
    for(int i = x; i >= 1; i /= 10){
        res += i % 10;
    }
    return res;
}

djm03178 5년 전 0

이분 탐색은 특정 지점에 대한 답을 구했을 때 그것만으로 그보다 작은 쪽이나 큰 쪽 어디로 이동해야 할지 알 수 있을 때만 사용할 수 있습니다.

하지만 decom의 반환값은 단조 증가가 아닙니다. 더 작은 수의 분해합이 더 큰 수의 분해합보다 클 수도 있습니다.

반례로는 117 (= 99 + 9 + 9)가 있습니다. 이 코드는 108을 출력합니다.

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

문제

문제

출처

ICPC

파라매트릭 서치

gshs340507 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말