반응형

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
반응형

1.  문제

■ URL : https://www.acmicpc.net/problem/1789

 

2. 핵심요약

■ 문제유형 : 탐욕(Greedy) 알고리즘

■ S: 자연수의 합 (문제의 Input)

■ N: 합계 S가 성립하는 자연수들의 최대 갯수

 

3. 문제풀이 접근

■ 최대한 많은 숫자를 이용하여 합계 S를 만들기 위해서는 가장 작은값(1)부터 차례대로 더해 나가야 한다.

■ 그 다음 더해지는 숫자를 고려하여 더해지는 값이 S 보다 더 크게 될때까지 카운트한다.

 

4. 파이썬 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
isTest = True
if isTest:
    f = open("./1789.txt", 'r')
    s = int(f.readline())
else:
    s = int(input())
 
current = 0
cnt = 0
 
adder = 1
 
while (s >= current):
    current += adder
 
    adder += 1
    cnt += 1
 
    if adder > s - current:
        break
 
print(cnt)
 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
26
27
28
29
30
let isTest = true
 
let fs = require('fs');
let input;
if (isTest) {
    input = fs.readFileSync('./1789.txt').toString().split('\n');
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n');
}
 
s = parseInt(input[0]);
 
current = 0
cnt = 0;
 
adder = 1;
 
while (s >= current) {
    current += adder;
    console.log(current);
 
    adder++;
    cnt++;
 
    if (adder > s - current) {
        break;
    }
}
 
console.log(cnt);
 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
반응형

1.  문제

■ URL : https://www.acmicpc.net/problem/2839

 

2. 핵심요약

■ 문제유형 : 탐욕(Greedy) 알고리즘

 

3. 문제풀이 접근

■ 먼저 큰 봉지(5kg)를 이용하여 설탕을 담는다.

■ 남은 분량을 작은 봉지(3kg) 단위로 배분하여 정확히 떨어지는지(나머지가 0) 여부를 확인한다.

■ 작은 봉지(3kg) 단위로 배분하여 떨어지지 않으면(나머지가 0 아님) 큰 봉지(5kg)의 갯수를 하나씩 줄인다.

■ 남은 분량이 작은 봉지(3kg) 단위로 배분하여 정확히 떨어지는면(나머지가 0) 봉지의 합이 최소값이 된다.

 

4. 파이썬 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
isTest = True
if isTest:
    f = open("./2839.txt", 'r')
    N = int(f.readline())
else:
    N = int(input())
 
answer = -1
for i in range(int(N / 5), -1, -1):
    remains = N - i * 5
 
    if remains % 3 == 0:
        answer = i + int(remains / 3)
        break
 
print(answer)
 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
let isTest = true
 
let fs = require('fs');
let input;
if (isTest) {
    input = fs.readFileSync('./2839.txt').toString().split('\n');
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n');
}
 
let N = input[0];
 
let answer = -1;
for(let i = parseInt(N / 5); i >= 0; i--) {
    let remains = N - i * 5;
 
    if (remains % 3 === 0) {
        answer = i + parseInt(remains / 3);
        break;
    }
}
 
 
console.log(answer);
 cs

 

반응형
저작자표시

'알고리즘(코딩테스트)' 카테고리의 다른 글

[백준] 주유소  (0) 2024.10.05
[백준] 수들의 합  (0) 2024.10.05
[백준] 읽어버린 괄호  (0) 2024.10.04
[백준] ATM  (1) 2024.10.03
[백준] 동전 0  (0) 2024.10.03
반응형

1.  문제

■ URL : https://www.acmicpc.net/problem/1541

 

2. 핵심요약

■ 첫째 줄에 식이 주어진다.

■ 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있다.

■ 가장 처음과 마지막 문자는 숫자이다. → 식의 가장 첫 부분은 양수로 시작한다.

■ 연속해서 두 개 이상의 연산자가 나타나지 않는다.

 

3. 문제풀이 접근

■ 문제의 내용을 종합하면 아래와 같은 형태를 만들어야만 식의 결과가 최소값으로 나타난다.

 

4. 파이썬 코딩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
isTest = True
if isTest:
    f = open("./1541.txt", 'r')
    input = f.readline()
else:
    input = input()
 
q_tkn_arr = input.split('-')
 
answer = 0
for i in range(len(q_tkn_arr)):
    sub_sum = 0
    s_tkn_arr = map(int, q_tkn_arr[i].split('+'))
    for s_tkn in s_tkn_arr:
        sub_sum += s_tkn
 
    if len(q_tkn_arr) == 1 or i == 0:
        answer = sub_sum
    else:
        answer -= sub_sum
 
print(answer)
 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
26
27
28
29
let isTest = true
 
let fs = require('fs');
let input;
if (isTest) {
    input = fs.readFileSync('./1541.txt').toString().split('\n');
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n');
}
 
let q = input[0];
q_tkn_arr = q.split('-')
 
answer = 0
for (let i = 0; i < q_tkn_arr.length; i++) {
    let sub_sum = 0;
    s_tkn_arr = q_tkn_arr[i].split('+').map(Number)
    for (let j = 0; j < s_tkn_arr.length; j++) {
        sub_sum += s_tkn_arr[j];
    }
 
    if (q_tkn_arr.length === 1 || i === 0) {
        answer = sub_sum;
    } else {
        answer -= sub_sum;
    }
}
 
console.log(answer);
 cs

 

반응형
저작자표시

'알고리즘(코딩테스트)' 카테고리의 다른 글

[백준] 주유소  (0) 2024.10.05
[백준] 수들의 합  (0) 2024.10.05
[백준] 설탕 배달  (0) 2024.10.04
[백준] ATM  (1) 2024.10.03
[백준] 동전 0  (0) 2024.10.03
반응형

1.  문제

■ URL : https://www.acmicpc.net/problem/11047

 

2. 핵심요약

■ 1번째 Row, 1번째 Col : 동전의 갯수

■ 1번째 Row, 2번째 Col : 주어진 동전 가격의 합으로 만들어야할 합계 가격

■ 2번째 Row 부터 : 각 동전의 가격

1
2
3
4
5
6
7
8
9
10
11
10 4790
1
5
10
50
100
500
1000
5000
10000
50000
 cs

 

 

3. 문제풀이 접근

■ 문제유형 : 탐욕(Greedy) 알고리즘

■ 최소한의 동전 갯수만 사용하기 위해 동전 단가가 큰 것부터 써야 한다.

■ 몫 연산자와 나머지 연산자 문법을 알고 주어진 합계 가격으로부터 필요한 동전의 갯수(최소값)을 구한다.

    - 파이썬 연산자 문법 : 나눗셈의 몫(//), 나눗셈의 나머지(%)

    - 자바스크립트 연산자 문법 : 나눗셈의 몫(/), 나눗셈의 나머지(%)

 

4. 파이썬 코딩

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
isTest = True
if isTest:
    f = open("./11047.txt", 'r')
    cnt, target = map(int, f.readline().split(' '))
else:
    cnt, target = map(int, input().split(' '))
 
arr = []
for i in range(1, cnt+1):
    if isTest:
        arr.append(int(f.readline()))
    else:
        arr.append(int(input()))
 
answer = 0
arr.reverse()
for item in arr:
    answer += target // item
    target = target % item
 
    if target == 0:
        break
 
print(answer)
 
 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
26
27
28
29
let isTest = true
 
let fs = require('fs');
let input;
if (isTest) {
    input = fs.readFileSync('./11047.txt').toString().split('\n');
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n');
}
 
let cnt = Number(input[0].split(' ')[0]);       // 동전의 갯수
let target = Number(input[0].split(' ')[1]);    // 목표값
 
arr = [];
for(let i = 1; i < cnt + 1; i++) {
    arr.push(Number(input[i]));
}
 
// 문제에서 동전의 가치는 이미 오름차순으로 주어짐.
answer = 0;
for(let i = arr.length - 1; i >= 0; i--) {
    answer += parseInt(target / arr[i]);
    target = target % arr[i];
 
    if (target === 0) {
        console.log(answer);
        return answer;
    }
}
 cs

 

 

반응형
저작자표시

'알고리즘(코딩테스트)' 카테고리의 다른 글

[백준] 주유소  (0) 2024.10.05
[백준] 수들의 합  (0) 2024.10.05
[백준] 설탕 배달  (0) 2024.10.04
[백준] 읽어버린 괄호  (0) 2024.10.04
[백준] ATM  (1) 2024.10.03

+ Recent posts

티스토리툴바