프로그래머스 고득점 Kit 중 동적계획법 문제 풀이
N으로 표현 문제 말고는 JS를 지원해주지 않아서 아쉬웠다
lv3. 정수삼각형
문제 요약
특정 위치까지의 숫자 합 점화식을 구하면 된다
triangle[row][col] = max(triangle[row-1][col], triangle[row-1][col-1])
회고
타일링 유형의 기본 문제인듯
from typing import List
def solution(triangle: List[List[int]]) -> int:
rows = len(triangle)
maxi = 0
for row in range(1, rows):
for col in range(row+1):
tmp = []
if col > 0:
tmp.append(triangle[row-1][col-1])
if col < row:
tmp.append(triangle[row-1][col])
triangle[row][col] += max(tmp)
if maxi < triangle[row][col]:
maxi = triangle[row][col]
return maxi
lv3. 등굣길
문제 요약
웅덩이를 피해 갈 수 있는 모든 최단 경로의 수
회고
- 타일링 유형
(m + 1) * (n + 1)2차원 배열 생성하고[1, 1]부터 시작하면 좀더 직관적으로 index 접근할 수 있음- 첫번째 행, 첫번째 열에서 Index Check할 필요 없이 0을 더하면 되기 때문에,
- 구현하기도 좀더 편리하고
- 조건 확인하는 연산 줄일 수 있음
from typing import List
def solution(m: int, n: int, puddles: List[List[int]]) -> int:
MOD = 1000000007
board = [[0 for i in range(m+1)] for j in range(n+1)]
for x, y in puddles:
board[y][x] = -1
board[1][1] = 1
for row in range(1, n+1):
for col in range(1, m+1):
if board[row][col] == -1:
continue
tmp = []
if board[row-1][col] != -1:
tmp.append(board[row-1][col])
if board[row][col-1] != -1:
tmp.append(board[row][col-1])
board[row][col] += sum(tmp)
return board[n][m] % MOD
lv4. 도둑질
문제 요약
- 원형 사이클 순회하면서 얻을 수 있는 최대 합
- 이때 특정 점의 양 옆 점은 선택할 수 없다
회고
- 입력이 최대 100만까지 주어질 수 있으므로
- 재귀를 사용하면 콜 스택 한도 초과 에러가 날 수밖에 없다
- 반복문을 사용할 수 밖에 없는데, bottom-up으로 구할 때 조건을 깔끔하게 세우는 데 애먹어서,
- 이 문제도 블로그 참고하여 해결..
- 참고: 얍문님 블로그
from typing import List
def solution(money: List[int]) -> int:
END = len(money)
maxi = 0
# 첫번째 집을 포함하는 경우: 0 ~ len -1
money0 = [0 for _ in range(END-1)]
money0[0] = money[0]
money0[1] = money[0]
for cur in range(2, END-1):
money0[cur] = max(money0[cur-2] + money[cur], money0[cur-1])
if money0[cur] > maxi:
maxi = money0[cur]
# 첫번째 집을 포함하지 않는 경우: 1 ~ len
money1 = [0 for _ in range(END)]
money1[1] = money[1]
for cur in range(2, END):
money1[cur] = max(money1[cur-2] + money[cur], money1[cur-1])
if money1[cur] > maxi:
maxi = money1[cur]
return maxi
lv3. N으로 표현
문제 요약
- 특정 수 N을 사용해 target number를 만들 수 있을 때,
- 최소 사용 횟수
회고
- 가장 발상이 어려웠던 문제
- 숫자를 가지고 DP하는 유형은 좀더 풀어봐야 할 것 같다
- 결국 이 문제도 다른 블로그 참고하여 해결함
- 참고: 구르미님 블로그
- Python으로 먼저 풀고 동일한 로직으로 JS로 풀었는데,
- 프로그래머스에서
console.log( /* Set 객체 */)를 했을 때 - 원소가 있는 경우에도
Set()으로만 표현되어서 디버깅이 힘들었다..
- 프로그래머스에서
Python 코드 및 채점 결과
def solution(N, number):
if number == N:
return 1
# memoization 초기화; target number가 0인 경우만 추가
memo = [{}]
# 1~8까지 순회하면서
for i in range(1, 9):
# N이 i개로 이루어진 수 추가
candidates = { int(str(N)*i) }
# 이전에 만들어진 수들 활용해 새로운 수 생성
# target == 4 일 때, 4 = 1+3 = 2+2 = 3+1이므로,
# 각각의 경우의 수를 모두 구해서 Set에 추가
for j in range(1, i):
for can1 in memo[j]:
for can2 in memo[i-j]:
candidates.add(can1 + can2)
candidates.add(can1 - can2)
candidates.add(can1 * can2)
if can2 != 0: candidates.add(can1 // can2)
# 만들어진 수 중 target number가 있으면 return
if number in candidates:
return i
memo.append(candidates)
# 위에서 수를 못 만든 경우는 -1 return
return -1
JS 코드 및 채점 결과
function solution(N, number) {
if (N === number) return 1;
const memo = Array.from({ length: 9 }, () => new Set());
for (let i = 1; i < 9; i++) {
memo[i].add(Number(N.toString().repeat(i)));
for (let j = 1; j < i; j++) {
memo[j].forEach((x) => {
memo[i - j].forEach((y) => {
memo[i].add(x + y);
memo[i].add(x - y);
memo[i].add(x * y);
if (y !== 0) memo[i].add(Math.floor(x / y));
});
});
}
if (memo[i].has(number)) return i;
}
return -1;
}
가볍게 TIL 남기는 velog, 꾸준히 성장하는 개발자