SWEA 22759. 묶음 판매

낱개와 X개 묶음으로 파는 물건을 N개 구매하려 할 때, N mod X가 X/2 보다 크거나 같다면 묶음을 산다고 할 때, 구매하려는 모든 물건 갯수에 묶음을 사게 하는 X가 있는지 확인하는 문제이다.

 

처음에는 구간 오른쪽(더 큰 수) 들에 대해서 구간 내부에 있는 구매 갯수 전부를 나머지 연산을 하려고 했으나 구간이 워낙 넓어 포기하였고, 특정 구간에 조건을 만족하는 X가 존재하는 조건인 구간의 시작과 끝의 차이가 2배 이상 나면 안되는 법칙을 찾게 되었다. 이유는 구간의 길이가 X 이상이 되면 N mod X가 X/2 이하인 구간이 존재하기 때문에 X는 구간 길이보다 큰 수가 된다. 또한 L mod X ≥ X/2 를 만족하게 되면 L ≥ X/2 즉, X ≤ 2L 가 되어 R - L < X ≤ 2L 인데 R >= 2L 인 경우 R - L < X ≤ 2L ≤ R - L 가 되어 X가 존재할 수 없게 된다.

핵심 조건 유도

X가 유효하려면 두 조건을 동시에 만족해야 한다.

조건 1 — 구간이 한 주기 안에 들어와야 함

X > R − L

연속된 X개의 정수 중에는 반드시 N mod X < X/2인 N이 존재한다.
따라서 구간 [L, R]의 길이(R−L+1)가 X 이상이면 X는 반드시 실패한다.

조건 2 — 구간의 시작점 L에서 조건 성립

L mod X ≥ X/2

조건 1에 의해 X > R−L ≥ L (R ≥ 2L이면) 이므로 X > L이면 L mod X = L.
따라서: L ≥ X/2 → X ≤ 2L

두 조건을 합치면:

R − L < X ≤ 2L

---

R ≥ 2L이면 왜 X가 없을까?

1. X가 유효하려면 X > R−L (하한)이어야 한다.
2. 동시에 X ≤ 2L (상한)도 만족해야 한다.
3. R ≥ 2L이면 R−L ≥ L, 즉 R−L ≥ 2L − L = L이 되어 R−L과 2L의 대소가 역전된다.
4. 결국 하한(R−L) ≥ 상한(2L)이 되어 X가 들어갈 공간이 사라진다.

한 줄 요약: R ≥ 2L이면 두 조건의 범위가 겹치지 않아 X가 존재하지 않는다.

결론: R < 2L 이면 X 존재 가능 / R ≥ 2L 이면 X 존재 불가

---

인터랙티브 시각화

슬라이더로 L과 R을 조절하며 X의 유효 범위가 어떻게 변하는지 확인해보세요.

X 존재 조건 수직선

R < 2L 이면 X 존재 · R ≥ 2L 이면 X 없음

L 5

R 8

✓ X가 존재합니다

 

X의 유효 범위: R−L < X ≤ 2L

 

범위 붕괴 (R ≥ 2L)

 

유효한 정수 X

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        while (tc-- > 0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken()), r = Integer.parseInt(st.nextToken());
            if (r >= l * 2) {
                sb.append("no").append('\n');
                continue;
            } else {
                sb.append("yes").append('\n');
            }
        }

        br.close();
        System.out.print(sb);
    }
}