백준 1065 [한수] : 파이썬 (브루트포스 알고리즘(Brute-force search))

📎 Problem

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

1065번: 한수

---

📎 Submission Code

두 가지 방법으로 풀이를 해보았는데, 결론적으로는 메모리는 30864KB로 동일하였고 시간은 68ms 또는 72ms로 비슷하였다.

1 ) 전체 - 한수가 아닌 수 빼기

한 자리 수인 1~9는 수열의 길이가 1인 등차수열로, 두 자리 수인 10~99는 길이가 2인 등차수열로 본다. 이해가 잘 가지 않는다면 여기를 클릭해서 참고하면 좋을 것 같다.

따라서 입력값이 최대 1000이므로, 세 자리 수 또는 네 자리 수(1000 1개)인 경우만 확인을 하면 된다.

세자리 수 일때는 등차수열의 정의에 따라 [세번째 자리(항) - 두번째 자리(항)] == [두번째 자리(항) - 첫번째 자리(항)] 즉, 공차(common difference)가 같지 않은 경우 한수가 아닌 수로 카운트 해준다.

마지막에 전체 수에서 한수가 아닌 수를 빼준다.

# case 1 : 한수가 아닌 수 카운트해서 전체에서 빼기 - 메모리 30864KB / 시간 68ms
import sys
num = int(sys.stdin.readline())
count = 0  # 한수가 아닌 수 카운트

for i in range(1, num + 1):
    # 길이가 3자리이거나 4자리일때만 확인(1자리 또는 2자리일때는 무조건 한수임)
    if len(str(i)) == 3 and (int(str(i)[2]) - int(str(i)[1])) != (int(str(i)[1]) - int(str(i)[0])): count += 1
    elif len(str(i)) == 4: count += 1

print(num - count)


# ---------------------------------------------------------------------------------
# case 1 : (함수로 만들기) 한수가 아닌 수 카운트해서 전체에서 빼기 - 메모리 30864KB / 시간 72ms
import sys
num = int(sys.stdin.readline())

def solve(num):
    count = 0  # 한수가 아닌 수 카운트

    for i in range(1, num + 1):
        # 길이가 3자리이거나 4자리일때만 확인(1자리 또는 2자리일때는 무조건 한수임)
        if len(str(i)) == 3 and (int(str(i)[2]) - int(str(i)[1])) != (int(str(i)[1]) - int(str(i)[0])): count += 1
        elif len(str(i)) == 4: count += 1

    return num - count

print(solve(num))

2 ) 한수인 수 카운트 하기

한수인 수를 카운트해보자. 99 이하 즉 두자리 수 이하인 경우에는 case1과 마찬가지로 한수로 취급하여 카운트를 해준다.(sum = 99)

세자리 수 이상일 때는, 첫번째 수 + 세번째 수(2a+2b) == 두번째수(a+b) * 2 인 경우를 확인하여 한수로 추가해준다.

이해가 잘 가지 않는다면 아래의 그림을 참고하자. 

# case 2 : 한수인 수 카운트 정리 - 메모리 30864KB / 시간 68ms
import sys
num = int(sys.stdin.readline())

if num <= 99: sum = num  # 3자리 수 이하일 때는 입력한 수 = 한 수
else:
    sum = 99  # 3자리 수 이상일 때는, 두자리 수까지는 한 수로 카운트하고 시작
    for i in range(100, num + 1):
        if i//100 + i%10 == ((i%100) // 10) * 2: sum += 1

print(sum)


# ---------------------------------------------------------------------------------
# case 2 : 한수인 수 카운트 이해하기
import sys
num = int(sys.stdin.readline())

if num <= 99: sum = num  # 3자리 수 이하일 때는 입력한 수 = 한 수
else:
    sum = 99  # 3자리 수 이상일 때는, 두자리 수까지는 한 수로 카운트하고 시작
    for i in range(100, num + 1):
        # 첫번째 수 + 세번째 수(2a+2b) == 두번째수(a+b) * 2
        if i//100 + i%10 == ((i%100) // 10) * 2:
            print(i)  # 한수인 수
            print(f"1 : {i//100}")  # 100으로 나눈 몫 : 첫번째 자리 수(a)
            print(f"2 : {i%10}")  # 10으로 나눈 나머지 : 세번째 자리 수(a+2b)
            print(f"3 : {(i%100 // 10) * 2}")  # 두번째 자리 수(a+b) * 2
            sum += 1

print(sum)

---

📎 Reference

• 위키백과 등차수열의 정의
• 백준 1065 [한수] 질문
• 개인 github 해당 문제 코드