[백준] 24313 - 알고리즘 수업 - 점근적 표기 1

Self-Solving

접근

• 단순하게 받아들여 문제를 $a_{1}n+a_{0} \leq c\times g(n)$ 중 $a_{1},a_{0},c,n_{0}$을 줄테니 이 조건에 부합하는 모든 n이 존재할 시 1을 출력하라고 해석하였다.
• 그래서 별 생각 없이 $a_{1}n+a_{0}$ 값이 $cn$ 보다 작을 경우 성립한다고 출력하면 되겠다고 생각하였다.

첫 번째 시도

  if(a0*n0+a1 <= c*n0) cout << 1 << endl;

 

이렇게 하니 90% 정도 되다가 말았었다.

두 번째 시도

케이스를 너무 덜 시도 했나? 라고 생각했었다. n0 하나만 보고 모든 n이 맞다고 가정하기엔 무리가 있을거 같다고 생각했기 때문이다. 그래서 수학적 귀납법을 흉내내어 n+1도 성립이 되는지 확인해보았다.

if(a0*n0+a1 <= c*n0 && a0*(n0+1)+a1 <= c*(n0+1)) cout << 1 << endl;

 

역시 90% 정도 되다가 말았었다.

세 번째 시도

계속 같은데에서 틀리니 문제 접근 방식이 틀렸다고 생각했다. 그래서 시간 복잡도의 수학적 접근을 보면서 곰곰히 생각해보았는데... 이 식 1차 방정식 그래프와 동일했다!!

1차 방정식 그래프는 선형인지라, 아주 정직하다. 어떠한 굴곡 없이 일직선으로 쭈욱 나간다. 대신 관측 지점이 중요한데, 처음에는 y값이 비교 대상 그래프보다 크더라도 특정 x값부터 더 작아질 수도 있다. 즉 두 그래프의 x값에 대응하는 y값을 비교할 때의 경우의 수는 모든 n에 대해 크거나, 작거나, 어느 지점에서 입장이 반전될 수 있다.

예시를 들어, 초록색 그래프는 x가 1 이하일 땐 y값이 파란색 그래프보다 컸지만, 2 이상일 경우엔 y값이 파란색 그래프보다 더 작아지는 것을 볼 수 있다.

 

따라서 위 방정식을 아래와 같이 전개할 수 있었다.

$a_{1}n+a_{0} \leq cn$

$a_{1}n+a_{0}-cn \leq 0$

$(a_{1}-c)n+a_{0} \leq 0$

여기서 $a_{1}$, $a_{0}$, $c$, $n_{0}$의 값이 정해진다. 여기서 n은 무조건적으로 양수이기 때문에 $(a_{1}-c)$이 음수이면서, $n_{0}$이 무엇이냐에 따라 모든 n에 대하여 부등식이 성립되냐 안되냐가 갈린다고 볼 수 있다.

 

이에 코드를 이렇게 작성할 수 있었다.

int abs(int n)
{
  if(n<0) return n*-1;
  else return n;
}
 
...

if(a1-c < 0 && abs(n0*(a1-c)) >= a0) cout << "1" << endl;

 

근데? 90%에서 또 멈췄다. 대체 왜...

최종 코드

곰곰히 생각해보다가, 이런 생각이 들었다. '$(a_{1}-c)$'의 값이 0인 경우면, n의 영향을 안받지 않나?'. 위의 코드를 보면 $(a_{1}-c)$가 무조건 음수여야한다고 조건문을 걸어뒀는데, 저 값이 0이 되더라도 남은 $a_{0}$ 값에 따라서 식이 성립할 수도 아닐 수도 있다. 왜냐면 평면 그래프 상에서 두 선형 그래프의 기울기가 같다고 가정했을 때 판가름이 나는 요소는 y절편 값이니깐 말이다.

이 두 그래프는 x가 극한으로 수렴하더라도 절대 만날 수가 없는 그래프이다. 즉, y값의 크기 순서가 뒤바낄 일 없이, 오로지 y절편 값을 통해 비교해줄 수 있다.

 

이에 코드를 수정하여 아래와 같이 최종 코드를 작성하였다.

#include <iostream>
using namespace std;

int abs(int n)
{
  if(n<0) return n*-1;
  else return n;
}

int main()
{
  int a0 = 0, a1 = 0, c = 0, n0 = 0;
  cin >> a1;
  cin >> a0;
  cin >> c;
  cin >> n0;
  if(a1-c <= 0 && abs(n0*(a1-c)) >= a0) cout << "1" << endl;
  else cout << "0" << endl;
  return 0;
}

 

성공!