BOJ 1065번 : 한수

안녕하세요. 지난 포스팅의 BOJ 4673번 : 셀프 넘버에서는 구현문제를 풀어보았습니다. 오늘도 마찬가지로 구현문제를 풀어보도록 하죠. 

 

완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다. 

 

핵심 포인트

• 1차원 배열 : 리스트 자료형
• 조건문
• 반복문

 

제출 코드

N = int(input())

if N < 100 : print(N)
else :
    cnt = 99
    for number in range(100, N + 1) :
        if 2 * ((number // 10) % 10) == number // 100 + number % 10 :
            cnt += 1
    print(cnt)

 

설명

이와 같이 수학과 관련된 구현문제를 저희는 이미 BOJ 1110번 : 더하기 사이클와 BOJ 4673번 : 셀프 넘버라는 문제에서 보았습니다. 이와 같은 문제의 핵심은 규칙을 정확하게 이해하고 간단한 예시에 적용해보는 것 입니다. 간단한 예로 한자리 숫자와 두자리 숫자에 대해서 생각해보면 어차피 등차수열을 이루기 위해서는 3개의 숫자가 필요하게 됩니다. 하지만, 1 ~ 99까지는 등차수열을 이룰 수가 없습니다. 다시 한번 문제의 조건을 보시면 저희는 "한수"를 카운트 해야합니다. 한수라는 것은 주어진 숫자의 각 자리수가 등차수열을 이룬다면 한수라고 하였죠. 그러나, 애초에 가정명제가 1 ~ 99에서는 성립하지 않기 때문에 집합론 - 교집합, 공집합, "If ... Then"의 의미에서 보았던 공허참(Vacuously Truth)에 의해 1 ~ 99는 결론에 관계없이 참이 됩니다. 

 

따라서, 저희는 100부터 고려해볼 수 있겠군요. 해당 숫자들이 $abc$와 같은 숫자로 되어 있다고 가정하겠습니다. 즉, $a, b, c$는 각각 백의 자리, 십의 자리, 그리고 일의 자리 수가 됩니다. 만약, 3개의 숫자들이 등차수열을 이룬다면 한수가 되는 것이죠. 따라서, 등차수열이 되기 위한 조건부터 생각해봅시다. 등차수열이라는 것은 연속된 두 숫자의 차이가 동일한 것을 의미합니다. 따라서, 두 숫자의 차이를 $d$라고 했을 때, $a, b, c$가 한수라면 $a = b - d$이고 $c = b + d$가 됩니다. 그리고 잘 보시면 $2b = a + c = (b - d) + (b + d) = 2b$가 성립한 것을 볼 수 있습니다. 즉, 각 자리의 수가 $2b = a + c$를 만족하면 $abc$는 한수가 되는 것이죠. 

 

그렇다면, $a, b, c$를 각각 추출하는 방법에 대해서 생각해봐야겠네요. $a$의 백의 자리이기 때문에 100으로 나눈 몫을 사용하면 됩니다. $b$는 십의 자리이기 때문에 10으로 나눈 몫을 다시 한번 10으로 나눈 나머지를 사용하면 되죠. $c$는 일의 자리이기 때문에 10으로 나눈 나머지를 사용하면 됩니다. 그래서 위 코드에서 2 * ((number // 10) % 10) == number // 100 + number % 10를 조건문으로 두었던 것입니다. 그리고 100보다 작은 수들은 모두 한수이기 때문에 cnt = 99로 시작하고 number를 100부터 N까지 순회하는 동안 조건문에 맞으면 1씩 더해주면 됩니다. 

 

참고자료 및 그림출처

백준 코딩 문제