배움과 성장/알고리즘·문제풀이
백준 1059 좋은 구간: 경계 두 개로 경우의 수 세기
백준 1059 좋은 구간은 모든 구간을 직접 만들기보다 n의 바로 아래·위 경계를 찾으면 풀리는 counting 문제다. 핵심은 “구간 안에 집합 S의 원소가 없어야 한다”는 조건을 endpoint 선택 범위로 바꾸는 것이다.현재 백준 1059번 원본 주소는 서비스 종료 안내가 표시된다. 이 글은 기존 글에 남아 있던 실제 문제 화면과 종료 전 공식 문제 페이지 archive의 조건·예제를 기준으로 검산했다.서비스 종료 전 백준 1059 문제 조건과 공식 예제좋은 구간의 조건두 자연수 A 로 만든 [A, B]가 좋은 구간이려면 구간 안에 S의 원소가 하나도 없어야 한다. 그중 n을 포함하는 구간의 수를 구한다.먼저 n이 이미 S에 있으면 답은 0이다. n을 포함한 어떤 구간도 “구간 안에 S의 원소가 없..