Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
Tags
- 플로이드-워셜
- 세그먼트 트리
- boj
- SSAFY
- 정렬
- 슬라이딩 윈도우
- 정수론
- DFS
- 모던 JavaScript 튜토리얼
- BFS
- 싸피
- 해시 테이블
- 2357
- 투 포인터
- 문자열
- 이분 탐색
- 애드 혹
- DP
- 그래프
- JavaScript
- Python
- 13164
- 수학
- 누적 합
- 트리
- 브루트포스
- 에라토스테네스의 체
- 그리디
- 맵
- 구현
Archives
- Today
- Total
흙금이네 블로그
[BOJ] 1106 - 호텔 (Python, JavaScript) 본문
아이디어
동적 계획법으로 고객 수에 따른 최소 비용을 계산한다.
풀이 #1 (Python)
고객 수에 필요한 최소 비용을 저장하는 C+1 크기의 리스트 dp를 생성하고, 초기값을 비용 최댓값 100,000으로 채운다.
for문에서 홍보 비용과 그 고객 수를 a와 b에 입력 받고, 고객 i명을 얻는 데 필요한 최소 비용 dp[i]를 갱신해 나간다.
b의 배수 이하의 고객을 얻는 비용을 그에 맞는 a의 배수와 비교해 더 작은 값으로 갱신한다.
또 고객 수 i에서 b만큼의 고객을 홍보 비용 a로 얻었을 때의 비용인 dp[i-b]+a와 비교해 더 작은 값으로 갱신한다.
import sys
input = sys.stdin.readline
def solution():
C, N = map(int, input().split())
dp = [100000]*(C+1)
for _ in range(N):
a, b = map(int, input().split())
for i in range(1, C+1):
if a*((i-1)//b+1) < dp[i]:
dp[i] = a*((i-1)//b+1)
if i > b and dp[i-b]+a < dp[i]:
dp[i] = dp[i-b]+a
print(dp[-1])
solution()
풀이 #2 (JavaScript)
풀이 #1과 마찬가지 방식으로 동작하며, 몫을 계산하기 위해 parseInt 함수를 사용한다.
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
const [C, N] = input[0].split(' ').map(Number);
let dp = Array(C+1).fill(100000);
for (let i=1; i<=N; i++) {
const [a, b] = input[i].split(' ').map(Number);
for (let j=1; j<=C; j++) {
if (a*parseInt((j-1)/b+1) < dp[j]) dp[j] = a*parseInt((j-1)/b+1);
if (j > b && dp[j-b]+a < dp[j]) dp[j] = dp[j-b]+a;
}
}
console.log(dp[C]);
'알고리즘' 카테고리의 다른 글
[BOJ] 5557 - 1학년 (Python) (0) | 2023.02.28 |
---|---|
[BOJ] 2268 - 수들의 합 7 (Python) (0) | 2023.02.28 |
[BOJ] 11003 - 최솟값 찾기 (Python) (0) | 2023.02.28 |
[BOJ] 15486 - 퇴사 2 (Python, JavaScript) (0) | 2023.02.23 |
[BOJ] 1275 - 커피숍2 (Python) (0) | 2023.02.22 |
Comments