Decision Problem

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

위 문제에서 처음으로 결정 문제(Decision Problem)에 대해 접하게 되었다. 

결정 문제의 정의는 다음과 같다. 

계산 이론에서 결정 문제(decision problem, 판정 문제)란 어떤 형식 체계에서 예-아니오 답이 있는 질문을 말한다.

예를 들어 "두 숫자 x와 y가 있을 때, y는 x로 나누어떨어지는가?" 하는 질문이 있다.

답은 x와 y 값에 따라 '예' 또는 '아니오' 중 하나가 될 수 있다.

일반적으로 계산 가능한 문제의 해집합은 열거 가능한 해집합(무한히 존재하는 해에 대해서는 결정 문제로 환원시킬 수 가

없다)의 유한한 부분집합이기 때문에,

대부분의 문제는 결정 문제로 환원될 수 있다.

최적화 문제의 구현이 어렵거나 해법이 떠오르지 않을 때는, Decision Problem으로 환원해서 생각을 해 보자!!

(시간 복잡도도 O(logN)으로 매우 빠르다)