귀류법 (2) 썸네일형 리스트형 (C++) - 백준(BOJ) 2217번 : 로프 www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net greedy문제였습니다. 풀이방법 1. 귀류법으로 greedy로 푸는 것이 합당한지 검증합니다. 귀류법이란 세운 명제에 반하는 명제를 세운 후 해당 명제가 거짓임을 보여 결론적으로 기존 명제가 참임을 증명하는 방법입니다. 먼저 가정을 세웁니다. 가정 : 들어올릴 수 있는 중량이 최대인 로프를 선택하면 최대 중량을 들어올릴 수 있다. 반하는 가정 : 들어올릴 수 있는 중량이 최소인 로프를 선택하면 최대 .. (C++) - 백준(BOJ)코딩 11047번 : 동전0 www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net greedy 문제였습니다. greedy로 푸는 것이 수학적으로 맞는지를 검증하는지가 중요합니다. 감으로 의존해 푸시면 제대로 문제를 풀 수 없습니다. 좋은 방법 중 하나는 귀류법으로 자신이 세운 가정이 맞는지를 증명해보는 것입니다. 귀류법을 통해 현재 최대 이익을 얻지 않으면 발생되는 손해가 있는지의 여부를 알 수 있습니다. 풀이방법 귀류법으로 증.. 이전 1 다음