분류 전체보기63 [BOJ/백준] 9461번 - 파도 단계별로 풀어보기 > 동적 계획법 1 > [4단계] 9461번 문제 링크 : https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 문제 요약 1. 주어진 문제에 대한 규칙을 찾아 점화식을 세운다. 입력 복사 예제 입력 1 >> 출력 : 3 16 2 6 12 CODE #include using namespace std; long long term[1000]; long long dp(int n) { if(n == 0 or n == 1 or n == 2) re.. 2021. 7. 9. [BOJ/백준] 11399번 - ATM 단계별로 풀어보기 > 그리디 알고리즘 > [3단계] 11399번 문제 링크 : https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 요약 1. 주어진 수에 대한 합의 최솟값을 구하기 위한 방법을 생각한다. 입력 복사 예제 입력 1 >> 출력 : 32 5 3 1 4 3 2 CODE #include using namespace std; #define endl "\n" int main() { int n; cin >> n; int t[1000]; for(int i=1; i> t[i.. 2021. 7. 2. [BOJ/백준] 1931번 - 회의실 배정 단계별로 풀어보기 > 그리디 알고리즘 > [2단계] 1931번 문제 링크 : https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 요약 1. 그리디 알고리즘을 사용하는 대표적인 스케쥴 문제 입력 복사 예제 입력 1 >> 출력 : 4 11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 CODE #include using namespace std; #define endl "\n" #define pb push_back #define mp make_pair typedef pair p; vector v; bool cmp(p a.. 2021. 7. 2. [BOJ/백준] 11047번 - 동전 0 단계별로 풀어보기 > 그리디 알고리즘 > [1단계] 11047번 문제 링크 : https://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 문제 요약 1. 그리디 알고리즘을 사용하는 대표적인 동전 문제 입력 복사 예제 입력 1 >> 출력 : 6 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 예제 입력 2 >> 출력 : 12 10 4790 1 5 10 50.. 2021. 6. 25. [C++] 그리디 알고리즘(1) - 동전 문제와 주의 사항 본 게시글은 "Competitive Programmer's Handbook"을 보며 임의로 해석하며 공부한 내용입니다. Greedy algorithms 그리디 알고리즘은 항상 그 순간에 가장 좋아보이는 선택을 함으로서 문제에 대한 해결책을 만든다. 그리디 알고리즘은 선택을 되돌리지 않고, 최종 솔루션을 직접 구성한다. 그러므로 그리디 알고리즘은 매우 효율적이다. 하지만, 설계 시 어려운 점은 문제에 대한 최적의 해결책을 제시하는 전략을 찾는 것이다. [대표 문제] Coin 문제 동전의 종류가 주어졌을 때, 동전을 사용하여 돈의 합계를 만드는 것이다. 동전의 가치는 coins = {c1, c2, c3, ...} 와 같이 주어지며, 동전 한 개당 원하는 횟수만큼 사용할 수 있다. 이때 필요한 최소 동전의 수.. 2021. 6. 25. 이전 1 2 3 4 5 6 7 8 ··· 13 다음 728x90 반응형
