20210115 // BaekJoon Online Judge // 1065

2021. 1. 15. 15:29Programming/BOJ

백준 알고리즘 BaekJoon Online Judge 1065번 "한수" 문제입니다.

N = input()

if len(N) <= 2:
  print(N)
elif len(N) == 3:
  k = 99
  for i in range(100, int(N) + 1):
    if (int(str(i)[0]) + int(str(i)[2])) / 2 == int(str(i)[1]):
      k += 1
  print(k)
elif len(N) == 4:
  print(144)

조금 생각하면 쉬운 문제라고 생각한다. 위의 풀이방법은 정석적인 풀이방법이 아닐 수 있겠지만 답만 맞으면 된거다.

 

한수의 개수를 구하는 문제인데 문제에서 한수란 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다.

 

등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다고 적혀있다. 그럼 생각해보자.

 

한 자리수일 경우는 전부 다 등차수열이다. 예를 들어 3은 3, 4, 5 .... 처럼 차이가 1인 등차수열의 항일수도 있고

 

3, 5, 7....처럼 차이가 2인 등차수열의 항일수도 있지만 아무튼 등차수열이라는 소리기에 한 자리수는 무조건 한수다.

 

두 자리수의 경우도 무조건 등차수열이다. 예를 들어 68의 경우 6, 8 즉 차이가 2인 등차수열이다.

 

11의 경우는 1, 1 차이가 0인 등차수열이다. 따라서 두 자리수도 무조건 한 수이다.

 

세 자리수의 경우만 잘 따지면 된다. 세 자리수일 경우는 계산을 해야 한다. 위 코드에서 사용한 방식은

 

등차수열 3개의 연속된 수가 주어지면 첫째 항과 셋째 항을 더하여 2로 나누었을 경우 둘째 항과 값이 같은 것을 이용한 것이다.

 

이는 만약 차이가 n인 연속된 등차수열 d, d+n, d+2n이 존재할 때 (d + d+ 2n) / 2 = d+n 으로 증명할 수 있다.

 

그리고 두 자리수는 모두 등차수열이라고 하였으므로 99까지의 한수의 개수는 99개 이므로 99개에서 위의 조건을 만족할 경우 1씩 더해주면 된다.

 

입력 값은 1000까지인데 1000은 한수에 해당하지 않으므로 999까지의 한수의 개수와 값이 동일하고 이는 144이다.

 

따라서 각 자리수에 대한 한수의 개수를 구하는 코드는 위와 같다.