판교의 메타몽

문제 링크 : https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 이 문제의 로직은 크게 다음과 같다. (1) 오름차순으로 방문 순서를 저장한다. 이때 유의해야할점이, n=3의 경우 {1},{1,2},{1,2,3}까지 방문하고 다시 {1,2}로 돌아가지 않도록 주의해야한다. 이럴 경우 아무리 배열의 최대 범위가 15까지라고 하더라고 시간초과가 날 수 밖에 없다. (2) 순서를 저장함과 동시에 여탯껏 저장한 순서들의 칼로리 + 돈을 계산한다. (2..

링크 : www.acmicpc.net/problem/7682 7682번: 틱택토 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 www.acmicpc.net 문제 풀이는 다음과 같다. 1. O가 X보다 많은 경우 2. O나 X를 연이어 두는 경우 3. YES빙고가 많거나, NO빙고가 많거나, YES빙고와 NO빙고가 같은 경우 3-(1) 각각의 경우에서 발생할 수 있는 invalid 조건을 서술한다 이 모든 경우 중 하나라도 해당되면 invalid가 나오고, 그렇지 않으면 valid가 나온다. #include #include using namespace s..

링크 : www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 풀이는 다음과 같다. 1. N+1일이 퇴사일이라는 점을 기억하자. 2. 백트래킹 - DFS를 통해 모든 경로를 구한다. 경로를 구하는 방법은 다음과 같다. (1) 현재 날짜에서 업무 날짜를 더한 값이 퇴사일을 초과하지 않으면 돈을 누적하여 dfs를 진행한다. (2) 현재 날짜의 다음날이 퇴사일을 초과하지 않으면, 해당일부터 또다시 새로운 dfs를 진행한다. #include #include #include using namespace std; int n, res, a, b = 0; vector v; vector ans(16, 0); v..

링크 : www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 전형적인 백트레킹 문제. 해당 문제는 주어진 값의 범위와, 로또의 당첨 숫자는 6개를 기억하면 문제없이 풀 수있다. * 2021/1/23 코드 수정 Memset과 배열을 활용한 풀이 #include #include using namespace std; bool ch[50] = {false,}; int n=0,temp=0,arr[14]; void dfs(int num, int cnt){ if(..

백 트래킹 (Back Tracking) 말 그대로 왔던 길을 다시 추적하는 알고리즘. 즉, 모든 경우를 전부 고려하는 알고리즘이다. 여기까지만 본다면 모든 경우를 하나하나 실험해보는 'Brute Force'가 떠오를 것이다. Brute Force와는 차별화된 Back Tracking의 특징은 필요없는 값은 정답 후보군을 제거해주는 가지치기(Pruning 혹은 Branch and bound)이다. 이 가지치기를 통해 한번 갔던 루트 중, 재방문이 필요없는 루트는 탐색하지 않는다. 백 트레킹에는 크게 3가지 종류가 있다. 스택 혹은 재귀함수를 이용하는DFS(깊이우선탐색, Depth First Search), 큐를 이용하는 BFS(너비우선탐색, Breadth First Search) BFS/HS(최선우선탐색,..