Scribbling

def solution(m, n, puddles): dp = [[0] * m for _ in range(n)] dp[0][0] = 1 for i in range(1, m): if [i+1, 1] in puddles: continue dp[0][i] = dp[0][i-1] for i in range(1, n): if [1, i+1] in puddles: continue dp[i][0] = dp[i-1][0] for i in range(1, n): for j in range(1, m): if [j+1, i+1] in puddles: continue dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[n-1][m-1] % 1000000007

굉장히 전형적인 DP 문제 def solution(triangle): h = len(triangle) dp = [[] for _ in range(h)] dp[0].append(triangle[0][0]) for i in range(1, h): dp[i].append(dp[i-1][0] + triangle[i][0]) for j in range(1, i): dp[i].append(max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j]) dp[i].append(dp[i-1][-1] + triangle[i][-1]) return max(dp[h-1])

난이도가 높지는 않은 문제. N을 1개씩 늘려가면서 완전탐색하되, number가 있는지 확인한다. 예컨대... 5가 네개인 경우를 완전탐색하려면, (5, 5, 5, 5) (5) + (5, 5, 5) (5, 5) + (5, 5) (5, 5, 5) + (5) 위의 모든 케이스를 다 따져 주면 된다. 여기서 +는 더하라는 의미가 아니라, 왼쪽에서 발생되는 모든 케이스와 오른쪽에서 발생되는 모든 케이스를 조합하는 모든 케이스를 생성하라는 의미이다. def solution(N, number): if number == N: return 1 dp = [[] for _ in range(9)] dp[1] = [N] for i in range(2, 9): dp[i].append(int(str(N)*i)) for j in ..

route들이 최대한 잘 겹치게 만드는 것이 목표인 문제이다. 이런 문제는 input의 순서를 강제하는 것이 큰 도움이 되는 경우가 많은데, 여기서는 routes를 사전에 정렬하는 것이 이에 해당된다. 정렬이 필요한 이유에 대해서는 생각해 볼 필요가 있는데, 이 문제에서는 group간 겹치는 문제를 회피하기 위해서이다. 아래 예제를 보자. [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] groups = [[-20, -15] 정렬하면, [[-20, -15], [-18, -13], [-14, -5], [-5, -3]] 1) [-18, -13] 처리 group 내의 [-20, -15]와 겹치므로 group[0]를 [-20, -15]와 [-18, -13]의 교집합인 [-18, -15]..

몸무게로 줄을 세우고, 돼지와 홀쭉이를 매칭시켜준다. def solution(people, limit): answer = 0 people.sort(reverse=True) i, j = 0, len(people) - 1 while i

def solution(number, k): stack = [] for num in number: while stack and stack[-1] 0: k -= 1 stack.pop() stack.append(num) return ''.join(stack[:len(stack)-k])

Generator를 이용한 해법 def solution(answers): def gen1(): candidates = [1, 2, 3, 4, 5] while True: for candidate in candidates: yield candidate def gen2(): candidates = [2, 1, 2, 3, 2, 4, 2, 5] while True: for candidate in candidates: yield candidate def gen3(): candidates = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] while True: for candidate in candidates: yield candidate g1 = gen1() g2 = gen2() g3 = gen3() ans..

x * y = brown + yellow (x-2) * (y-2) = yellow --> 모든 정수 조합 완전 탐색 def solution(brown, yellow): answer = [] xy_product = brown + yellow candidates = [] for i in range(1, xy_product//2+1): if xy_product % i == 0: candidates.append((xy_product//i, i)) for candidate in candidates: if (candidate[0]-2) * (candidate[1]-2) == yellow: return candidate

def solution(numbers): def is_prime(number): if number == 1: return False i = 2 while i * i

딱 봐도 정렬 후 Binary Search하면 된다. 매번 그렇듯 프로그래머스 지문은 극혐이다. from bisect import bisect_left def solution(citations): answer = 0 citations.sort() l, r = 0, citations[len(citations) - 1] while l = mid: answer = max(answer, mid) l = mid + 1 else: r = mid - 1 return answer