알고리즘

문제 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주 www.acmicpc.net 풀이 그리디 기타 줄을 사는 경우는 총 3가지이다. 패키지만 사서 N줄을 채우는 경우 낱개만 사서 N줄을 채우는 경우 패키지와 낱개 혼합으로 사서 N줄을 채우는 경우 여기서 필요한 값은 패키지 가격의 최솟값, 낱개 가격의 최솟값이다. 3번의 경우 최솟값인 패키지를 (N / 6)개 구입해서 남은 줄인 (N % 6)줄을 낱개로 구입하는 것이 가격이 최소다. 위의 3가지 경우 중에서 최솟값을 구한다. 코드 #include #include using names..

문제 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 풀이 그리디, 정렬 먼저 서류심사 성적을 기준으로 정렬한다. 서류 성적 1등부터 7등을 0번부터 6등이라고 하자. 서류 면접 1 4 2 5 3 6 4 2 5 7 6 1 7 3 0번은 서류 성적이 1등 이므로, 면접 성적이 낮아도 서류 성적이 제일 높기 때문에 무조건 선발된다. 1번은 0번보다 서류 성적은 낮지만, 면접 성적이 높을 수 있다. 1번이 0번보다 면접 성적이 높다면 설발된다. 1번이 선발되었다고 가정하자. 마찬가지로, 2번은..

문제 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 풀이 그리디 0과 1의 구역 중에서 더 적은 수의 구역을 뒤집으면 된다. S[i]와 S[i + 1]의 문자가 서로 다르면, 한 구역이 종료된 것으로 S[i]의 구역 수를 1 증가한다. 문자열의 끝까지 검사하여, 개수가 더 적은 구역의 수를 출력한다. 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); s..

문제 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 풀이 그리디 가장 작은 자연수인 1부터 N을 넘기 직전까지 더해간다. N이 200이면 다음과 같다. 1 + 2 + 3 + ... + 18 + 19 = 190 다음 수인 20을 더하면 210이므로 200을 초과한다. 여기서 더해지는 자연수는 중복되면 안 되므로, 마지막 수인 19를 29로 바꾸면 합이 200이 된다. 즉, 1부터 더한 값이 넘을 때까지의 자연수의 개수 - 1이 정답이다. 코드 #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); ..

문제 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 그리디, 우선순위 큐 카드 수가 가장 적은 2개의 묶음을 합치는 방식으로 해결할 수 있다. 이 때, 2개의 묶음을 선택하기 위해, 우선순위 큐를 사용한다. 카드 수가 가장 적은 2개의 묶음을 합친다. 합쳐진 묶음을 다시 우선순위 큐에 넣는다. 모든 카드 묶음이 합쳐질 때까지 반복 코드 #include #include using namespace std; // 오름차순 우선순위 큐 priority_queue pq; int main() { ..

문제 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 그리디 현재까지 지나온 지역 중에서 가장 기름이 싼 기름을 미리 사는 방식으로 해결한다. 현재 지역보다 가격이 싼 지역이 등장할 때까지, 현재 지역에서 기름을 구매하고 이동한다. 이를 반복해서 마지막 지역에 도착한다면 종료한다. // 현재 지역의 오른쪽 지역 중에서, 현재 지역의 가격보다 기름이 싼 지역이 발견되면 다음 목적지로 설정한다. for (int i = current; i ..

문제 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 풀이 그리디 로프들 중에서 무게를 많이 견딜 수 있을 만큼 로프를 골라야 한다. 무게를 많이 버틸 수 있는 로프부터 고르는 것이 최선의 방법이므로, 로프를 내림차순으로 정렬한다. 정렬한 로프를 앞에서부터 탐색한다. i번째 로프에서 최대한 버틸 수 있는 무게는 (i번째로프가 견딜 수 있는 무게) * (i 까지 로프의 수)이다. 이 방법으로 최대 무게를 찾는다. 코드 #include #include using namespace std; int nums..

문제 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net 풀이 그리디 기본적인 그리디 알고리즘 문제. 큰 동전부터 거스름돈을 최대한 처리한다. 코드 #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; int change = 1000 - N; int coins[6] = { 500, 100, 50, 10, 5, 1 }; int cur..

문제 2725번: 보이는 점의 개수 첫째 줄에 테스트 케이스의 개수 C(1

문제 10166번: 관중석 KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지 www.acmicpc.net 풀이 수학, 유클리드 호제법 좌석을 분수로 생각한다. 반지름이 i이면서 j번째 좌석은 i / j로 표현한다. i1 / j1과 i2 / j2가 기약분수로 표현했을 때, 같은 값을 가진다면, 한 좌석은 다른 좌석을 가리게 된다. D1부터 D2까지의 좌석을 기약분수로 나타냈을 때, 중복되는 경우 답에 추가하지 않는다. 코드 #include using namespace std; // 좌석을 분수로 표현 bool nums[2001][2001]; int gcd(int ..