C++156 [백준] 2623번 - 음악프로그램 (C++) 문제 및 풀이 문제) 백준 - 위상 정렬 - 음악프로그램 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net passed 배열로 출연 여부를 확인한다. 위상 정렬로 res에 push_back 하면서 res의 size()가 n보다 작으면 0을 출력한다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/2623_%EC%9D%.. 2021. 10. 5. [백준] 2056번 - 작업 (C++) 문제 및 풀이 문제) 백준 - 위상 정렬 & DP - 작업 https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 위상 정렬 아이디어와 DP를 이용하여 풀 수 있는 문제. ACM Craft문제와 비슷하여 그렇게 풀려고 했지만, Top-Down으로 푸는 거 포기... n번째 사람까지 걸리는 작업 시간을 memoization 하면 된다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blo.. 2021. 10. 1. [백준] 4811번 - 알약 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법(Dynamic Programming) - 알약 https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net cache[w][h]: 약 w(한 조각), h(반 조각)의 개수 memoization solve(w, h): top-down방식으로 알약 한 조각 먹을수 있는 경우(w > 0), 반 조각 먹을 수 있는 경우(h > 0)를 더해서 return C++ 소스코드) Full code) https://github.com/Chocochip101/BO.. 2021. 9. 29. [Codeforces] Codeforces Round #743 (Div. 2) - A) Countdown (C++) 문제 및 풀이 문제) Codeforces - 구현 - A) Countdown https://codeforces.com/contest/1573/problem/A Problem - A - Codeforces codeforces.com 맨 끝자리가 아닐 경우, cnt를 하나씩 증가시키면서 자릿수를 더해 나간다. C++ 소스코드) 2021. 9. 29. [백준] 20040번 - 사이클 게임 (C++) 문제 및 풀이 문제) 백준 - 분리 집합 - 사이클 게임 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 분리 집합을 이용하여 쉽게 풀 수 있는 문제. 선분을 그리면 같은 집합으로 merge하고 parent가 같을 경우 사이클이 있는 것으로 간주한다. C++ 소스 코드) ps. 사이클에 꽂혀서 dfs만 주구장창 생각했다... 2021. 9. 28. [백준] 11653번 - 소인수 분해 (C++) 문제 및 풀이 문제) 백준 - 정수론 - 소인수분해 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 소인수분해 기본 문제. k를 2부터 증가시키면서 나눠질 경우 출력 후 나눈다. C++ 소스코드) 2021. 9. 27. [백준] 14881번 - 물통 문제 (C++) 문제 및 풀이 문제) 백준 - 정수론 - 물통 문제 https://www.acmicpc.net/problem/14881 14881번: 물통 문제 용량이 a, b 리터인 두 물통이 있다. 이때, 물을 적절히 부어서 정확하게 c리터를 만들 수 있는지 아닌지 구하는 프로그램을 작성하시오. 물은 무한히 많다. www.acmicpc.net 용량이 a인 물통과 b인 물통으로 용량 c를 만들어야 한다. a와 b로 만들 수 있는 가장 작은 단위의 물통을 생각해보면 최대 공약수임을 알 수 있다. 따라서 a와 b의 최대공약수를 이용해 물통 c를 채울 수 있으면 성공, 아니면 실패인 것이다. C++ 소스코드) 2021. 9. 24. [백준] 1972번 - 놀라운 문자열 (C++) 문제 및 풀이 문제) 백준 - Set, HashMap - 놀라운 문자열 -> https://www.acmicpc.net/problem/1972 1972번: 놀라운 문자열 대문자 알파벳으로만 이루어져 있는 문자열이 있다. 이 문자열에 대해서 ‘D-쌍’이라는 것을 정의할 수 있는데, 이 문자열에 포함되어 있는, 거리가 D인 두 문자를 순서대로 나열한 것을 이 문 www.acmicpc.net 입력으로 주어지는 문자열의 길이가 80을 넘지 않고 입력의 줄 수가 101줄을 넘지 않으므로 Set을 이용하여 D-쌍들을 하나씩 탐색하여 놀라운 문자열인지 판별할 수 있다. C++ 소스코드) 2021. 9. 23. [백준] 2631번 - 줄세우기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 (Dynamic Programming) - 줄세우기 -> https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 이미 정렬되어 있는 아이들 제외하고 정렬되지 않는 아이들을 옮긴다. 이때 옮겨지는 아이의 최소 수를 구해야 되므로 정렬되어 있는 아이들의 최대 수(Lis)를 구하여 전체 아이들의 수(n)에서 빼준다. C++ 소스코드) 2021. 9. 3. 이전 1 ··· 11 12 13 14 15 16 17 18 다음 반응형
