반응형 PS 문제 풀이/SWEA75 [SWEA] 3421 수제 버거 장인 출처: SWEA Approach 버거를 만들 때, 재료가 하나도 없는 것도 하나의 버거가 될 수 있다. 즉, N개의 자료 중에 하나도 선택하지 않는 경우도 포함해야 한다. 조합(combination) 을 구현한다. - 재료 자체를 중복해서 선택할 수 없다. ▶ 순열과 조합 순열과 조합 (백준 N과 M 시리즈) 순열과 조합 순열(Permutation) / 조합(Combination)에서 개수를 구하는 경우에는 ▶ P(n, r) = n × (n - 1) × (n - 2) × ... × (n - r - 1) = n! / (n - r)! 상황에 따라서는 주어지는 Data가 나올 수.. zoosso.tistory.com ▶ N과 M (2) (중복 허용하지 않는 조합) [BOJ] 백준 15650 N과 M (2) 출.. 2021. 5. 16. [SWEA] 4411 덕환이의 카드 뽑기 출처: SWEA Approach 조세푸스 점화식을 구현하는 문제이다. #include #define ULL unsigned long long ULL N, K, r; int tc, TC; int main() { // freopen("input.txt", "r", stdin); scanf("%d", &TC); for (tc = 1; tc 2021. 5. 16. [SWEA] 1267 작업순서 출처: SWEA Approach 선행 조건이 있으면 사이클이 존재하지 않는다고 명시되어 있다. 이는 위상정렬을 구현하는 문제이다. 위상정렬 (Topological sort) 위상정렬 (Topological sort) 개념 DAG에서 의존성에 맞게 그래프의 정점을 정렬 DAG (Directed Acyclic graph) 간선에 방향이 존재하고, 사이클(cycle)이 없는 그래프. DAG는 노드간의 의존성을 나타내는데, 작업 간의 순서를 표현하는 zoosso.tistory.com 코드에서는 DFS할 때, 후속 작업이면서 아직 방문하지 않은 정점을 DFS 탐색하고 아직 처리되지 않은 선행 정점(작업)이 존재하는 경우 분기한정 처리하였다. DFS (depth-first search, 깊이 우선 탐색) 깊이 우선.. 2021. 5. 16. [SWEA] 10204 초밥 식사 출처: SWEA Approach Greedy 문제로 A와 B가 본인의 행복도를 높이면서 상대방의 행복도를 낮추어야 한다. 🤷♀️ 모든 경우의 수 탐색하면 TLE 발생 문제 해결한 방법은 초밥(접시)에 {A의 행복도} + {B의 행복도}의 합을 기준으로 정렬한다. (자신의 행복도를 최대화 하며서, 상대방 행복도를 최소화 하기위한 전략) 그리고 A와 B가 번갈아가며 먹었을 때, 행복도를 계산하는 것이다. (N이 짝수가 아닐 수 있으므로 A가 B보다 한번 더 먹고 끝날 수 있다.) #include #define LL long long const int MAX_N = 1e5 + 5; struct Info { int ah, bh; LL sum; }food[MAX_N], tmp[MAX_N]; inline void.. 2021. 5. 16. [SWEA] 3238 이항계수 구하기 출처: SWEA Approach 뤼카의 정리와 페르마의 소정리를 적용하면 풀 수 있는 문제이다. #include #define LL long long const int MAX_N = 1e5 + 2; int tc, TC; LL ans, fact[MAX_N]; LL X, Y, n, r, p; int main() { // freopen("input.txt", "r", stdin); scanf("%d", &TC); for (tc = 1; tc 2021. 5. 16. [SWEA] 1232 사칙연산 출처: SWEA Approach 이진트리를 구성한 다음 후위순회를 하는 문제이다. 아래 Input Case를 분석해보자. Input 1 - 2 3 2 - 4 5 3 10 4 88 5 65 Output 13 - 1번 노드에 (-) 연산과 자식노드로 2, 3번 노드 - 2번 노드에 (-) 연산과 자식노드로 4, 5번 노드 - 3번 노드에 10, 4번 노드에 88, 5번 노드에 65 트리 형태는 아래와 같다. ▶ (88 - 65) - 10 = 23 - 10 = 13 트리 형태 구현은 구조체를 이용한다. 후위 순회는 아래처럼 구현한다. 부모 노드에서 연산자(+ - * /)에 해당하는 경우 왼쪽 자식 노드 & 오른쪽 자식 노드로 재귀 탐색해서 연산 결과를 return 받는 방식이다. 후위 순회말고도 전위 / 중위.. 2021. 5. 15. [SWEA] 1259 금속막대 출처: SWEA Approach Input Data로 주어지는 N이 명확하게 주어지지 않은 문제이다. 그렇기에 N 의 최대값에 따라 배열 크기 설정을 해야 하는데 "input.txt"에 있는 Test Case 중 가장 큰 값으로 제출했는데 문제가 없었다. 문제에서 명시하지 않은 조건 중 고려해볼 수 있는 조건은 크게 2가지이다. - 수나사 값끼리 중복이 없다. 마찬가지로 암나사끼리도 중복이 없다. - 연결해서 최대 길이를 구했을 때, 남는 나사가 없다. 즉, 모든 남사를 연결했다고 볼 수 있다. 순열과 조합 순열과 조합 (백준 N과 M 시리즈) 순열과 조합 순열(Permutation) / 조합(Combination)에서 개수를 구하는 경우에는 ▶ P(n, r) = n × (n - 1) × (n - 2) .. 2021. 5. 14. [SWEA] 3314 보충학습과 평균 출처: SWEA Input 1 10 65 100 30 95 Output #1 68 입력받은 점수가 40점 미만인 경우, 40점으로 처리하여 합산하여 평균을 구하면 됩니다. #include using namespace std; int main(){ int testCase; cin >> testCase; for (int tc = 1; tc > temp; if (temp < 40) temp = 40; sum = sum + temp; } cout 2021. 3. 1. [SWEA] 3142 영준이와 신비한 뿔의 숲 출처: SWEA Input 2 5 3 7 5 Output #1 1 2 #2 3 2 이차방정식을 통해서 풀이 - 유니콘의 수 unicon, 트윈혼의 수 twinHorn ▶ unicon + 2twinHorn = n ▶ unicon + twinHorn = m → twinHorn = n - m → unicon = m - twinHorn #include using namespace std; int main(){ int testCase; cin >> testCase; int n, m, unicon, twinHorn; for (int tc = 1; tc > n >> m; twinHorn = n - m; unicon = m - twinHorn; cout 2021. 3. 1. [SWEA] 3066 팀 정하기 출처: SWEA Input 3 6 3 2 2 1 1 6 10 3 Output #1 2 #2 0 #3 3 팀을 구성하기 위해서는 여자 인원수에 2배에 해당하는 남자인원 수가 필요합니다. 그렇기에 남자 10명 / 여자 2명일 때, 남자 6명은 인턴 여부를 떠나 팀을 구성하지 못합니다. 반대로 남자 2명 / 여자 10명일 때, 여자 9명은 인턴 여부를 떠나 팀을 구성하지 못합니다. 팀을 구성하지 못하는 인원에 대한 인턴 인원을 처리한 후, 팀을 구성할 수 있는 최대 경우의 수를 구합니다. #include using namespace std; int men, women, K, target; int main() { int testCase; cin >> testCase; for (int tc = 1; tc > me.. 2021. 3. 1. 이전 1 2 3 4 5 ··· 8 다음 반응형
