그리디 알고리즘

[13164] 행복 유치원(C++)

문제 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다. 이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자. 입력 입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K..

[1049] 기타줄

https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 🔎 해결 방법 정렬을 한 후 제일 첫번째 원소를 취하던지, 아니면 입력받을 때마다 비교를 하던지 해서 패키지 가격의 최솟값과 낱개 가격의 최솟값을 찾아야 한다. 그리고 이 두 개의 값만 사용하면 문제를 풀 수 있다! 1. 모두 낱개로 사는게 제일 싼 경우 예를 들어 가장 싼 패키지 가격이 24, 가장 싼 낱개의 가격이 3이라면 항상 낱개로 사는 것이 더 이득이다. 따라서 (가장 싼 낱개 가격)..

[2437] 저울(C++)

🎅🏻 문제 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓� www.acmicpc.net 🧣 해결 방법 예를 들어 추의 무게가 (3, 1, 6, 2, 7, 30, 1) 이렇게 주어졌다면 오름차순 정렬을 하고 처음부터 각 인덱스까지의 추의 무게를 합한 sum 은 아래의 표와 같다. sum = 처음부터 각 인덱스까지의 추의 무게의 합 즉, sum에 저장된 값에 해당하는 무게까지는 우리가 만들 수 있다는 뜻이 된다. ex) sum = 7이면 무게가 1인 것부터 7인 것까지 모두 만들 수 있다는 뜻 i가 4일때부터 한번 차근차근 봐보자. 1) i = 4,..

[10610] 30

https://www.acmicpc.net/problem/10610 10610번: 30 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶� www.acmicpc.net 🔎 해결 방법 우선 30의 배수가 되기 위해서는 두 가지를 만족해야 한다. 일의 자리가 0 각 자리의 합이 3의 배수 따라서 코드도 이런식으로 짜면 된다. ✍️ 알고리즘 1. string으로 문자열을 입력받은 후, sort 함수를 사용해서 오름차순으로 정렬한다. ex) 입력 : 80875542 -> 정렬한 후 : 02455788 2. 문자열의 첫번째 원소가 0인지 확인 0이라면 30의 배수가 되..

[2352] 반도체 설계(C++)

문제 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 🔎 해결 방법 이 문제는 [11053] 가장 긴 증가하는 부분 수열과 같이 왼쪽 포트는 이미 오름차순으로 정렬이 되어 있으므로 이와 연결된 두번째 포트가 어떻게 해야 가장 긴 증가하는 부분 수열을 이루는지를 찾으면 된다. 그래서 처음에는 [11053] 가장 긴 증가하는 부분 수열 문제를 해결한 것과 같이 이중 for문을 사용한 dp로 해결하려고 했다. 하지만 틀렸습니다가 떠서 질문들을 찾아보니 대부분 "LIS" 라는 알고리즘을 사용하여 ..

[1120] 문자열

https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 � www.acmicpc.net 🔎 해결 방법 현재 순간에서 가장 최선의 경우만 고려하는 그리디 알고리즘의 특성을 이용하면 생각보다 코드도 짧고 간단한 문제였다. 예를 들어 A = "adaabc", B = "aababbc" 라면 먼저 (B[0], A[0]), (B[1], A[1]), (B[2], A[2]) ... 이런식으로 비교를 한 다음, 다른 경우에만 gap을 증가시켜 주면 된다. ..

[1138] 한 줄로 서기

문제 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. www.acmicpc.net 🔎 해결 방법 현재 상태에서 최선인 것만 보는 그리디 알고리즘을 사용해서 풀어야 하는 문제이기 때문에 말 그대로 모든 것을 현재 상황 기준으로 결정하면 된다. 예를 들어 줄을 서야 하는 사람의 수가 5명이고, 자신보다 왼쪽에 있는 사람 중 키 큰 사람의 수를 담고 있는 left배열이 다음과 같이 주어진다고 가정하자. 우선 키가 1인 사람부터 보면 1인 사람의 왼쪽에는 키가 1보다 큰 사람이 2명 있어야 한다. ..

[5585] 거스름돈(C++)

문제 5585번: 거스름돈 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 예를 들어 입력된 예1의 경우에는 아래 그림에서 처럼 4개를 출력해야 한다. 입력 입력은 한줄로 이루어져있고, 타로가 지불할 www.acmicpc.net 내 코드(C++) // [5585] 거스름돈 // https://www.acmicpc.net/problem/5585 #include using namespace std; int main(void) ..