그리디 알고리즘 기초문제 풀이

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

11047번: 동전 0

동전 0

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

119991

63272

48664

51.972%

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

 

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

예제 입력 1 

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 1 

6

예제 입력 2 

10 4790
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 2 

12

 

이 문제는 거스름돈 문제의 업그레이드 버전이라고 할 수 있습니다.

거스름돈으로 줄 수 있는 화폐의 종류또한 입력으로 받기 때문입니다.

화폐의 종류를 배열에 담고 거슬러 줄 때는 하나씩 차례대로 처리하면 됩니다.

다만 항상 화폐의 가치가 큰 것 부터 나누어 줘야하므로 처리할 때는 순서를 거꾸로하여 처리해야합니다.

 

const fs = require('fs');
let [N, ...nums] = fs.readFileSync('dev/stdin').toString().trim().split(/\s+/).map(Number);

let price = nums.shift();

function money(k) {
  let count = 0;
  const arr = nums.sort((a, b) => b - a);;
  for(let item of arr){
    count = count + Math.floor(k/item); //동전의 개수
    k = k - item * Math.floor(k/item); // 남은 돈 계산
  }
  return count;
}
console.log(money(price));

 

https://www.acmicpc.net/problem/11399

 

 

 

---

ATM

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

91544

61810

49607

68.026%

문제

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

예제 입력 1 

5
3 1 4 3 2

예제 출력 1 

32

 

 

const fs = require('fs');
const [n, input] = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const inputArr = input.trim().split(" ").map((x)=>Number(x))

inputArr.sort((a,b)=>a-b);
let result=0;
for(var i=0;i<n;i++){
	for(var j=0;j<=i;j++){
		result+=inputArr[j];
        }
}
console.log(result);

 

---

https://www.acmicpc.net/problem/2217

 

로프

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

192 MB

54982

24109

19323

42.845%

문제

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1 복사

2
10
15

예제 출력 1 복사

20

 

 

const fs = require('fs');
const input = fs.readFileSync("./dev/stdin").toString().trim().split('\n').map(Number);
const N = input.shift();
const rope = input.sort((a,b)=>a-b); //오름차순 정렬
let arr=[];
for(let i=0;i<N;i++){
    //사용된 로프 중에 단 한 개라도 중량을 견딜 수 없어서는 안 되므로, 
    //로프들을 사용하여 들어올릴 수 있는 물체의 최대 중량은 
    //(버틸 수 있는 최대 중량이 가장 낮은 로프) X (로프의 개수)와 같다.
    //오름차순 정렬 후 작은 순으로 최대 중량이 가장 낮은 로프를 하나씩 배제하면서 할 수있는 최대중량을 넣는다.
    arr.push(rope[i]*(N-i));
}
console.log(Math.max(...arr))

즉 [5,10,15] 에서 

5 10 15 모두 사용하면 15를 들 수 있고, (버틸 수 있는 최대 중량이 가장 낮은 로프) * 3

10 15 를 모두 사용하면 20을 들 수 있고, (버틸 수 있는 최대 중량이 가장 낮은 로프) * 2

15를 모두 사용하면 14를 들 수 있다. (버틸 수 있는 최대 중량이 가장 낮은 로프) * 1

 

 

 

 

 

---

https://www.acmicpc.net/problem/1138

한 줄로 서기

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

11341

6628

5532

59.305%

문제

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. i는 0부터 시작한다.

출력

첫째 줄에 줄을 선 순서대로 키를 출력한다.

예제 입력 1 

4
2 1 1 0

예제 출력 1 

4 2 1 3

---

예제 입력 2 

5
0 0 0 0 0

예제 출력 2 

1 2 3 4 5

---

예제 입력 3 

6
5 4 3 2 1 0

예제 출력 3 

6 5 4 3 2 1

---

예제 입력 4 

7
6 1 1 1 2 0 0

예제 출력 4 

6 2 3 4 7 5 1

---

 

const fs = require('fs');
let [N, ...nums] = fs.readFileSync('dev/stdin').toString().trim().split(/\s+/).map(Number);

let n = N;
let arr=Array(n).fill(0);
for(var i=1;i<=n;i++){
	let count =0;
    let x = nums[i-1];
    for(var j=0;j<n;j++){
    	if(count == x && arr[j]==0){
        	arr[j]=i;
            break;
        }
        if(arr[j]==0) count++;
    }
}
console.log(arr.join(" "));

1. 먼저 [2, 1, 1, 0] 이면  1번사람은 왼쪽에 키큰 두명이 보이는 것이다.

2. 1번부터 먼저 왼쪽에 두명이 보이도록 2칸을 오른쪽으로 가서 3번째에 선다.

3. 2번사람은 왼쪽에 키 큰 한명이 보인다.

4. 그럼 1칸만 오른쪽으로가서 2번째에 선다.

5. 3번사람은 왼쪽에 키 큰 사람이 한명 보인다.

6. 그럼 원래는 1칸만 오른쪽으로 가야하는데 2번째와 3번째에는 2번사람과 1번사람이 서있다.

7.그래서 3번 사람은 그 둘을 건너뛴 4번째에 선다.

8. 4번사람은 왼쪽에 키 큰 사람이 없으므로 1번째에 선다.

 

1번사람

 

2번사람

 

3번사람

4번사람

 

즉 1 2 3 4 번호는 사람의 키를 뜻하고,

주어진 2, 1, 1, 1은 왼쪽에 키큰사람이 있냐 없냐다.

 

어차피 작은사람은 키가 큰 사람에게 안보이므로 키가 제일 작은 1번부터 세워야한다.

그래서 만약 1번부터 줄을 세우면서 줄에 사람이 아직 안서있다면 그 빈자리는 자기보다 키 큰 사람이 들어가는 곳이다.

즉 1번사람은 2명이 키큰 사람이 있어야하므로 2칸을 오른쪽으로 간 것이다.

 

 

 

 

---

 

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

1541번: 잃어버린 괄호

잃어버린 괄호

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

69874

37213

29230

52.589%

문제

세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.

그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.

괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.

출력

첫째 줄에 정답을 출력한다.

예제 입력 1 복사

55-50+40

예제 출력 1 복사

-35

예제 입력 2 복사

10+20+30+40

예제 출력 2 복사

100

예제 입력 3 복사

00009-00009

예제 출력 3 복사

0

 

 

마이너스가 등장한 순간부터는 부호에 상관없이 무조건 계산을 마이너스로 한다.

즉 문자열을 하나씩 검사하면서 부호가 아니면 숫자를 저장하고

만약 부호를 만나면 minus를 이전에 만났었는지 확인한다.

아니면 현재 부호를 계산하고

이후 현재 부호가 minus면 minus를 만났었음을 저장한다.

다음 계산부터는 부호를 만날 때 무조건 minus계산을 한다.

이때 마지막 숫자를 만나고 부호를 만나지않기 때문에 계산이 멈추게된다.

i>=arr.length 이러한 조건을 줘서 마지막 숫자까지 계산할 수 있게 한다.

 

const fs = require('fs');
const arr= fs.readFileSync("/dev/stdin").toString().trim();
let minus=false;
let result=0;
let temp="";
for(var i=0;i<=arr.length;i++){
	if(arr[i]=="+" || arr[i]=="-" || i>=arr.length){
    	if(minus==true) {
        	result+=-Number(temp)
        }
        else {
        	result+=Number(temp);
        }
        temp="";
        if(arr[i]=="-") {
            minus=true;
        }
        continue;
    }
    temp+=arr[i];
}
console.log(result);

 

---

https://www.acmicpc.net/problem/10610

10610번: 30

 

 

문제

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.

 

입력

N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

출력

미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.

예제 입력 1 

30

예제 출력 1 

30

예제 입력 2 

102

예제 출력 2 

210

예제 입력 3 

2931

예제 출력 3 

-1

예제 입력 4 

80875542

예제 출력 4 

88755420

 

 

숫자들을 재조합하여 가장 큰 30의 배수를 만드는문제다.

이때 각 자리의 모든 숫자의 합이 3의 배수이면 전체 숫자는 항상 3의 배수가 된다는 정수론의 기초개념을 이해해야한다.

따라서 각 숫자 자릿수의 합이 3의 배수인지 확인하고, 0이 포함되어있어야 30의 배수가 가능하므로 0의 포함여부도 확인한다.

 

const fs = require('fs');
let input = fs.readFileSync("/dev/stdin").toString().trim();

let num = Array(10).fill(0); //숫자 0~9의 출현횟수를 저장하기위한 배열
let sum=0;
let result=""
for(var i=0;i<input.length;i++){ //주어진 문자열의 숫자의 출현횟수를 저장한다.
	num[Number(input[i])]++;
    sum+=Number(input[i]); //이때 문자열 각각의 숫자들의 총 합을 구한다
}
//총합이 3으로 나뉘면 3의 배수임은 증명하는 정수론의 기초개념을 활용
//그리고 0의 자리가 하나라도 있어야 30배수가 됨
if(sum%3==0 && num[0]!=0){
	for(var i=9;i>=0;i--){ //가장 큰 숫자부터 차례로 빼냄
    	for(var j=0;j<num[i];j++){ //가장 큰 숫자의 출현횟수를 모두 빼냄
        	result+=String(i); //result에 붙임
        }
    }
}
else result=-1; //아니면 -1

console.log(result)

 

 

---

https://www.acmicpc.net/problem/1946

1946번: 신입 사원

 

신입 사원 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

51116

17151

12540

32.360%

문제

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

출력

각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

2
5
3 2
1 4
4 1
2 3
5 5
7
3 6
7 3
4 2
1 4
5 7
2 5
6 1

예제 출력 1 복사

4
3

현재 점수가 아닌 순위로 주어진다.

즉 순위에 따라서 비교를 해야된다.

먼저 서류심사 순위로 오름차순 정렬을 한다.

그렇게되면 1등 2등 3등... 이렇게 되고 옆에 면접순위가 따라오게 될것이다,

[1,4],[2,3],[3,2],[4,1],[5,5] 이렇게 되는데

[1,4]와 [2,3]을 비교해본다 그럼 서류 2등의 면접순위가 더 높은것을 확인할 수 있다.

그러므로 [1,4]와 [2,3]은 합격이다. 그리고 최소등수 값인 [2,3]을 비교하는 수로 넣어준다.

그다음 [2,3]과 [3,2]를 비교한다. 이번에도 ,[3,2]는 합격이다.

이런식으로 반복하면된다.

 

 

const [T,...input] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

for(var i=0;i<T;i++){
	let N = input.shift();
    let arr= input.splice(0,N).map(v=>v.split(' ').map(Number)).sort((a,b) => a[0]-b[0]);
    let count = 1;
    let tmp = arr[0][1];
    for(let i=1;i<N;i++){
        if(tmp > arr[i][1]){
        	tmp=arr[i][1];
            count++;
        }
        if(tmp==1) break;
    }
    console.log(count);
    
}