728x90 C 썸네일형 리스트형 [백준알고리즘] 2217번: 로프 -C [백준알고리즘] 2217번: 로프 -C https://www.acmicpc.net/problem/2217 2217번: 로프 N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 www.acmicpc.net Greedy Algorithm이 DP보다는 역시 생각하기가 쉬운 것 같다. 일단 위 문제를 풀기 위해서.. 더보기 [백준알고리즘] 11399번: ATM -C, Python [백준알고리즘] 11399번: ATM -C, Python https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 그리디 알고리즘의 대표적인 예라고 생각하는 문제이다. 이 문제는 CPU scheduling 기법 중 하나인 SJF(Shortest Job First)을 알고 있다면 쉽게 풀 수 있는 문제이다. 이 문제도 마찬가지로 처리시간이 짧은 순서대로 정렬을 해서 처리를 해주면 된다. 다른 분들은 이 부분을 위해서 시간복잡도가 빠른 퀵 정렬 등을 사용해서 정렬을 해주었지만, 여기서 .. 더보기 [백준알고리즘] 2293번: 동전 1 -C [백준알고리즘] 2293번: 동전 1 -C https://www.acmicpc.net/problem/2293 단계별로 풀어보기 마지막 '동적 계획법 1'의 마지막 문제였다. 그래서 기쁜 마음으로 봤는데 생각보다 쉬워서 흡족했다..ㅎㅎ 처음에는 일단 가볍게 동전 가치의 내림차순으로 정렬한 후에 재귀를 사용해서 해봤다. 역시나 시간초과가 발생했다. 그래서 다음에 사용한건 nsize와 target의 크기를 입력받아 nsize x target행렬을 만든 것이다. 이때부터는 점화식을 사용했기 때문에 내림차순 정렬이 필요없어진다. 사용했던 점화식은 다음과 같다. dp[i][j] = dp[i - 1][j] + dp[i][j - nlist[i]] (i번째 동전없이 j가치를 만들 수 있는 방법의 수) + (i번째 동전을.. 더보기 이전 1 2 다음