반응형
1. 문제
■ URL : https://www.acmicpc.net/problem/13305
2. 핵심요약
■ 문제유형 : 탐욕(Greedy) 알고리즘
■ 1번째 Row: 도시의 개수를 나타내는 정수
■ 2번째 Row: 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 구성
■ 3번째 Row: 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 구성
3. 문제풀이 접근
■ 첫번째 도시에서는 가격에 상관없이 주유를 할 수밖에 없다.
■ 두번째 도시부터는 다음(오른쪽) 도시들의 가격과 비교하여 미리 주유 여부를 결정한다.
4. 파이썬 코딩
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
isTest = True
if isTest:
f = open("./13305.txt", 'r')
city_cnt = int(f.readline())
distArr = list(map(int, f.readline().split(' ')))
priceArr = list(map(int, f.readline().split(' ')))
else:
city_cnt = int(input())
distArr = list(map(int, input().split(' ')))
priceArr = list(map(int, input().split(' ')))
sum = 0
minPrice = priceArr[0]
for i in range(len(priceArr) - 1):
if minPrice > priceArr[i]:
minPrice = priceArr[i]
sum += minPrice * distArr[i]
print(sum)
|
cs |
5. JavaScript 코딩
|
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
|
let isTest = true
let fs = require('fs');
let input;
if (isTest) {
input = fs.readFileSync('./13305.txt').toString().split('\n');
} else {
input = fs.readFileSync('/dev/stdin').toString().split('\n');
}
city_count = parseInt(input[0]);
distArr = input[1].split(' ').map(Number);
priceArr = input[2].split(' ').map(Number).slice(0, city_count - 1);
let sum = BigInt(0);
let minPrice = priceArr[0];
for (let i = 0; i < priceArr.length; i++) {
if (minPrice > priceArr[i]) {
minPrice = priceArr[i];
}
sum += BigInt(minPrice) * BigInt(distArr[i]);
}
console.log(String(sum));
|
cs |
반응형
'알고리즘(코딩테스트)' 카테고리의 다른 글
| DFS(Depth First Search; 깊이 우선 탐색) 파이썬 / 자바스크립트 구현 (1) | 2024.11.12 |
|---|---|
| [백준] 수들의 합 (0) | 2024.10.05 |
| [백준] 설탕 배달 (0) | 2024.10.04 |
| [백준] 읽어버린 괄호 (0) | 2024.10.04 |
| [백준] ATM (1) | 2024.10.03 |