[BOJ] 1527: 금민수의 개수 + 파이썬의 Product?

개인적으로는.. 알고리즘 문제 푼 걸 블로그에 올려두지는 않는 편이다. 하지만 특정 코딩테스트를 준비할 때마다 짧고 굵게 공부를 하는 편인데 문제를 풀면서 새로 알게된 지식들이나 어려웠던 문제는 조금조금씩 기록을 해두려고 한다.

 

문제링크

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

1527번: 금민수의 개수

 

풀이

from itertools import product

a, b = map(str, input().split(' '))
la, lb = len(a), len(b)

result = 0
for i in range(la, lb+1):
  combList = list(product([4, 7], repeat = i))
  for comb in combList:
    number = int(''.join(map(str, comb)))
    if int(a) <= number <= int(b):
      result += 1

print(result)

 

풀이해석

먼저, 이 문제에서 주어진 수가 10억으로 엄청 큰 수가 주어졌다. 그래서 우리는 이걸 Brute-force로 일일이 탐색하려고 하면 말이 안되겠죠? 그런데 문제를 보면 4와 7로만 이루어진 수만 찾으면 되기 때문에 일일이 탐색할 필요가 없다. 그래서 우리는 4와 7로만 이루어진 수를 만들고, 특정 2개의 수 사이의 숫자인지만 확인하면 된다.

 

그렇기 때문에 우리는 a와 b라는 숫자를 받아서 a와 b가 각각 몇자리 수인지만 확인하면 된다. 어짜피 4와 7로만 이루어진 수를 만들 것이기 때문이다. 예를 들어 a가 2자리 숫자라면 44, 47, 74, 77 총 4가지 숫자가 만들어 질 것이고, 3자리 숫자라면 총 8가지의 숫자조합이 만들어질 것이다.

 

하지만 여기서 필자는 product라는 라이브러리 메서드가 있는지 몰랐다. 그래서 이 숫자 조합을 특정 파라미터로 받아서 어떻게 만들까 많이 고민을 했다. 둘다 n자리 숫자라고 고정이 되어있으면 쉬운데, 서로 다른 자릿수 숫자일 수도 있기 때문에 더 골치아팠다.

 

결국 많은 시간을 투자해도 방법이 잘 떠오르지 않아서 인터넷 검색을 해서 product라는 메서드가 있는지 확인했다. product는 중복순열을 만들어주는 메서드이고, 사용방법은 위의 코드를 참고하면 될 것 같다. 우리가 구현하고자 하는 걸 이 product를 통해 쉽게 구현할 수 있었다.

 

proudct로 각 자릿수의 순열 리스트를 만들어주고, a와 b 사이의 숫자면 count만 증가시켜주면 끝나는 문제이다.  product만 알면... 쉽게 풀었을 문제같다.

 

추가 설명

하지만 분명히 product 없이도 문제를 풀 수 있을 것만 같았는데 못풀어서 너무 자존심이 상했다.... 보니까 DFS를 통해 문제를 해결할 수 있었을 것 같다.

def dfs(lower, upper, depth, num):
  result = 0

  if depth >= 10 or num > upper:
    return 0
  if lower <= num <= upper:
    result += 1

  result += dfs(lower, upper, depth+1, num*10+4)
  result += dfs(lower, upper, depth+1, num*10+7)

  return result

a, b = map(int, input().split(' '))
result = dfs(a, b, 0, 0)
print(result)

 

위의 풀이는 다른 분의 풀이를 가져와 봤다. 너무 잘 풀어주신 것 같아서.. 존경스럽다.

 

- 먼저, depth가 10을 넘을 수 없다. 최대 10억이기 때문에 depth는 자릿수를 의미하는데 최대 9까지 가능하다.

- 그리고 num은 upper를 넘으면 안된다. upper는 b이다. 최대 b까지 가능하기 때문에 조건을 걸어줬다.

- 그리고 num이 lower(a)와 upper(b) 사이면 카운팅을 추가해준다.

- 우리는 이 과정을 재귀를 통해 할 것이다. 이 때 depth는 1씩 추가해주고, num은 4와 7만 이루어질 수 있도록 수식을 적어주면 된다.

 

이런 방법을 생각못했다니....! 너무 아쉽다.

---

참고자료

- https://codedrive.tistory.com/404

[BOJ]1527. 금민수의 개수