Brute Force

문제 https://leetcode.com/problems/smallest-divisible-digit-product-i 풀이 n보다 큰 수 중에서 각 자리수의 곱이 t로 나눌 수 있는(나머지가 0인 ) 가장 작은 수를 리턴해야 한다. 문제의 제약조건이 $1 <= n <= 100$, $1 <= t <= 10$ 이라서 모든 수를 찾아봐도 된다. 정수의 각 자리수를 모두 곱한 수를 구하는 로직만 구현한 후에, n 부터 시작해서 숫자를 1씩 증가시키면서 t로 나눈 나머지를 구해서 찾으면 된다. 코드 class Solution: def smallestNumber(self, n: int, t: int) -> int: def productDigits(x: int) -> int: product = 1 while x > 0: product *= x % 10 x //= 10 return product answer = n while productDigits(answer) % t != 0: answer += 1 return answer

문제 https://www.acmicpc.net/problem/14658 풀이 우선 최악의 경우를 생각해보자. N, M이 각각 500,000 이고, L은 1, K가 100일 때가 최악인 경우가 된다. 이 상태에서 모든 경우의 수를 확인하려면 별의 위치를 250,000,000,000,000번 확인해야 한다. 따라서 모든 경우의 수를 판단하는건 불가능 하다. 따라서 트램펄린을 설치할 위치를 합리적으로 정해야 한다. 주어진 조건을 보면 별이 최대 100개 까지밖에 없으므로 이를 활용하여 생각해본다. 우선 별 하나를 기준으로 보면 L * L 크기의 트램펄린이고, 별이 최대 100개 있으므로 확인해야 할 위치는 최악의 경우에 100,000,000,000,000개 이다. 사실상 위의 경우와 다를바가 없으므로 불가능하다. ...