[백준/BOJ] 24313번 알고리즘 수업 - 점근적 표기 1 (Node js/ Javascript)

24313번: 알고리즘 수업 - 점근적 표기 1 (acmicpc.net)

24313번: 알고리즘 수업 - 점근적 표기 1

구현 부분이 간단한데도 불구하고 난이도가 실버인 이유가 있다. 문제를 이해하는 것 부터 힘들었다..

 

문제해설

처음 문제를 다 이해하기도 전에 일단 구현 했을 때는, f(n) <= g(n) * c 부분을 조건으로 걸어 0과 1을 출력하도록 했었다.

그런데 채점이 80퍼가 넘어가길래 살짝 기대했건만 아니나 다를까 91퍼에서 오답 처리가 되었다.

그래서 반례를 여기서 찾아보다가 a0 부분을 음수로 해보라는 이야기가 많아서 일단 a0를 음수로 하는 여러가지 입력들로 시도해 보다가 이해가 됐다.

 

아래는 처음 91퍼에서 오답 처리 됐던 코드이다.

const fs = require("fs");

const input = fs.readFileSync("../input.txt").toString().trim().split("\n").map((item)=> item.split(" "));

var a1 = Number(input[0][0]);
var a0 = Number(input[0][1]);
var c = Number(input[1][0]);
var n0 = Number(input[2][0]);

var fn = (a1*n0) + a0;

if(fn <= n0*c){
    console.log(1);
}else{
    console.log(0);
}

4 -3
3

1

입력을 위와 같이 넣고 실행 해보면 1이 나올 것이다. 하지만 이것은 틀렸다. 왜냐하면 입력의 마지막 줄 n0을 1에서 4로 바꿔 보면 -1이 나오는데, 1을 출력하기 위해서는 n >= n0 인 모든 상황에서 fn <= n0*c 이란 조건을 만족해야 하기 때문이다. 

 

이러한 반례가 발생한 이유는 아래 그래프를 보면 알 수 있다. 그래프의 a0, a1, c값들은 이해를 돕기 위해 내가 임의로 준 값 들이니, 문제의 조건과는 부합하지 않을 수 있다.

 

먼저 a0가 0일 경우의 그래프이다. a1은 2이고 a0를 0, c를 1.5로 했다. O(n)을 만족하려면 파란선 즉 g(x)가 빨간선 보다 위에 있어야 하는데 그렇지 않으니 0을 출력할 것이다. 정상적인 모습이다

이번엔 a0가 양수일 경우의 그래프이다. a1은 2이고 a0를 5, c를 1.5로 했다. 마찬가지로 빨간선이 파란선 위에 있으니 O(n)의 조건에 실격이다.

이번엔 a0가 -5일 때이다.

이럴수가, 10이 넘어간 부분의 빨간선 - f(x)가 파란선 - g(x) 위에 있으니 O(n) 정의에 부합하지 않다. 그런데, 기존 내 로직은 x가 1일때를 보고 판단 할테니, 파란선이 빨간선 위에 있어서 O(n) 정의에 맞다고 출력하여서 반례가 발생했던 것이다.

 

이런 일이 생긴 이유는 f(x)의 기울기가 g(x)의 기울기보다 크지만, f(x)의 y절편이 음수인 바람에, x 좌표가 0과 가까운 쪽에 g(x)가 f(x)보다 y 좌표값이 큰 곳이 생겼기 때문이다. 

 

 

전체코드

const fs = require("fs");

const input = fs.readFileSync("../input.txt").toString().trim().split("\n").map((item)=> item.split(" "));

var a1 = Number(input[0][0]);
var a0 = Number(input[0][1]);
var c = Number(input[1][0]);
var n0 = Number(input[2][0]);

if(a0<0) n0 = n0 - a0;  

var fn = (a1*n0) + a0;

if(fn <= n0*c){
    console.log(1);
}else{
    console.log(0);
}

"if(a0 < 0) n0 = no - a0;" 이 로직을 통해 a0가 음수일 경우, x좌표가 1인 부분을 확인하는게 아니라, 1 - (a0)에서 확인함으로써 O(n) 정의에 부합하지 않는 것을 부합한다고 보는 경우를 차단했다.