백준 24313 - 파이썬

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

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

 

문제 풀이

이번 문제 역시 처음에 읽고 무슨 소리인지를 몰라 당황했다. 하지만 천천히 읽어보니 함수 f(n) = a1*n + a0와 양의 정수 c와 n이 주어질 경우 O(n)의 정의가 f(n) <= c * g(n)일 때 O(n)을 만족하는지를 구하면 되는 문제였다. 문제가 어려워 보이지 않았고, 바로 코드를 작성해 봤다.

 

a1,a0 = map(int, input().split())
c = int(input())
n = int(input())

def f(n):
    return a1*n + a0

def g(n):
    return n

if f(n) <= c * g(n):
    print(1)
else:
    print(0)

 

하지만 91%를 넘어가니 틀렸다고 했다. 틀린 부분이 어딘지 찾아내고자 했는데 이해가 되지 않아서 구글링을 해봤다. 여러 사람들의 블로그를 들어가서 읽어보니 a0가 음수인 경우도 생각해야 하기 때문에 조건식에 a1 <= c가 추가되어야 한다고 하는데, 설명을 읽어봐도 많은 부분이 생략된 설명인거 같아 쉽사리 이해되지 않았다. 또한 스스로 생각하기에 n0와 n이 항상 같은 값이 들어가는것을 보면서 그렇다면 굳이 n0라고 표현할 필요가 있을까 싶긴 했지만 이 부분에 대한 이유를 더 명확히 찾지 못했다. 그러다가 이 블로그에서 힌트를 얻었다. 아무리 다른 사람들의 설명을 읽어봐도 이해를 하지 못한 이유가 사실 문제 자체를 잘못 이해했기 때문이었다.

 

a1, a0 = map(int, input().split())
c = int(input())
n0 = int(input())

flag = True
for n in range(n0, 101):
    if a1 * n + a0 > c * n:
        flag = False

if flag:
    print(1)
else:
    print(0)

 

flag = True
for n in range(n0, 101):
    if a1 * n + a0 > c * n:
        flag = False

 

이 코드를 보면 n0부터 100까지 반복되고, 그 값이 n에 들어갔다. 즉, 이 문제의 핵심은 f(n) <= c*n이라는 식이 주어졌을 때 우리가 입력한 값이 여기에 해당하는지 안 하는지를 판별하라는 것이 아니라 O(n)정의에 만족하는지를 판별하라는 문제였기에 n0부터 100까지 모든 숫자가 다 대입해보고 단 한번의 오류도 없을 때 참을 출력하라는 것이었다. 나는 이 부분을 놓친 것이었다. 그럼 이번에는 a1 <= c라는 식이 추가됐어야 하는 이유에 대해 정리해 보겠다.

 

a1,a0 = map(int,input().split())
c = int(input())
n0 = int(input())

if a1*n0 + a0 <= c*n0 and a1 <= c:
    print(1)
else:
    print(0)

 

수식을 정리해보면 간단히 알 수 있는 부분이다.

 

여기서 부등식이 n의 값과 상관없이 a0보다 크려면 (c-a1)은 양수여야 한다. 음수인 경우 n이 커질수록 더 작아지기 때문이다. 위 식을 코드로 나타내면 다음과 같다.

 

a1,a0 = map(int, input().split())
c = int(input())
n = int(input())

result = 1
f = a1*n + a0
if f > c*n:
    result = 0
if c-a1 < 0:
    result = 0

print(result)

 

 

느낀점

이번 문제는 문제를 얼마나 꼼꼼히 잘 읽고, 주어지 조건들을 빠짐없이 정확하게 수행하였는지가 중요했던거 같다. 문제를 99% 맞춰도 조건 하나를 빠뜨려 100%를 채우지 못한다면 그것 또한 풀지 못한 것이니 조건들을 빠짐없이 수행하기 위해 노력해야 되겠다.