문제

---

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

틀린 풀이

---

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader( new InputStreamReader(System.in));

        /*
        입력
         */
        String input = br.readLine();
        int a1 = Integer.parseInt(input.split(" ")[0]);
        int a0 = Integer.parseInt(input.split(" ")[1]);

        int c = Integer.parseInt(br.readLine());
        int n0 = Integer.parseInt(br.readLine());

        /*
        입력받은 값으로 f(n)과 g(n) 계산
         */
        int Fn = a1 * n0 + a0;
        int Gn = c * n0;

        /*
        출력
         */
        if (Fn > Gn)  
            System.out.println("0");
        else
            System.out.println("1");
    }
}

💡 반례

예제로 주어진 것들은 제대로 나오는데 채점 결과 틀리다고 나와서 고민하다가..
결국 백준에서 질문게시판을 참고해보니, 반례로 다음 입력을 넣어보라는 답변이 있었다.

7 -2
6
1

분명 양수만 입력가능한 것 같았는데? 하고 다시 문제를 찬찬히 살펴보니
0 ≤ |a0| ≤ 100, 0 ≤ |a1| ≤ 100
절댓값이 양수였다.. 하하

---

반례처럼 a1 = 7, a0 = -2, c = 6인 경우

f(n) = 7*n - 2
g(n) = 6*n

반례에서는 n0 = 1 이므로,
f(n)=5 <= g(n)=6으로 조건을 만족해서 1이 출력된다.

그러나 n0보다 큰 모든 n에 대하여 f(n) <= g(n)이어야 한다는 점을 다시 생각해보자!!
n=3만 되어도 f(n)=19 > g(n)=18 로 조건을 충족하지 못한다.

기존에는 n0보다 큰 수가 들어오는 것이니 가장 작은 n0만 비교해도 된다고 생각했지만,
a0이 음수이고 n0이 작은 수일때 한시적으로 f(n) <= g(n)인 것을,
n0보다 큰 모든 n에서 f(n) <= g(n) 이라고 잘못 판단되는 것이다!

올바른 풀이

---

f(n)과 g(n)모두 1차 방정식이니
상수인 a0과 관계없이 1차항의 계수가 큰 쪽이 n이 커지면서 결국 커지게 된다.

따라서, f(n)과 g(n)의 1차항의 계수를 비교하는 코드를 추가하면 된다!
a1 > c 인지를 비교하는 구문을 추가하였다.

        /*
        출력
         */
        if (Fn > Gn || a1 > c)  // a0이 음수일 수 있으므로 'a1 > c' 도 비교!!
            System.out.println("0");
        else
            System.out.println("1");

느낀점

반례가 떠오르지 않아 한참을 고민했다😥
결국 게시판에서 다른 분이 올려주신 반례를 보았지만, 그래도 바로 틀린 부분을 파악하고 올바른 풀이를 생각해낼 수 있었다!

앞으로는 문제를 꼼꼼히 보고, 직접 반례를 찾아보는 연습을 하자!!