GGym's Practice Notes

간단한 DP문제다. 위에서 아래로 내려오면서 값을 저장하고 맨 아래에서 제일 큰 값을 출력하면 된다. 백준에도 똑같은 문제가 있다. ( 옛날에 DP 모를때 고생했던 문제..) www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net #include // Level3_ 정수삼각형 [DP] #include #include #include using namespace std; int solution(vector triangle) { int answer = 0; vector dp; vector first; first.push_back(triang..

BFS를 이용하여 가장 먼 노드를 찾는다. 최단거리 탐색법을 사용하여 계산하면 좀 더 깔끔하게 나오겠지만 BFS를 사용하는 것이 더 쉬워보인다. DFS로 풀어보려다가 계속 시간초과나서 포기했다. #include // Level3_ 가장 먼 노드 [BFS] #include #include #include #include #include using namespace std; bool visit[20001]; int dst[20001]; int solution(int n, vector edge) { int answer = 0; vector graph(n, vector(n, false)); queue q; for(int i=0; i n >> k; for(int i=0; i k; edge[i].push_back(..

이분탐색 문제이다. 심사관이 맡을 수 있는 사람의 수 += 걸리는 추청 시간 / 심사관이 심사하는데 걸리는 시간 이 공식을 알아야지 문제를 풀 수 있다. 사람의 수가 많거나 같다면 최저시간을 저장한 후 추정시간을 늘리고 적다면 추정시간을 줄여본다. #include // Level3_ 입국심사 [이분탐색] #include #include #include using namespace std; long long solution(int n, vector times) { sort(times.begin(), times.end()); long long l=0, r = (long long)(times[times.size()-1]) * n; long long answer = r; while(l> n >> n_t; for..

비교적 쉬운 Level3 문제 DFS나 BFS를 쓰면 간단하게 풀 수 있다. 나는 연습삼아 BFS를 사용했다. #include #include #include using namespace std; bool visit[200]; void bfs(int v, int n, vector computers){ queue q; visit[v] = true; q.push(v); int now; while(!q.empty()){ now = q.front(); q.pop(); for(int i =0; i

규칙을 찾아보면 그냥 피보나치랑 똑같다. DP로 착각할 수 있고 풀 수도 있겠지만 속도차이가 있을까... #include #include #include using namespace std; int solution(int n) { int answer=0; if (n == 1) answer = 1; else if (n == 2) answer = 2; else for(int i=2, j=1, k=2; i

Vector로 되어있는 입력 데이터를 Stack으로 옮긴 후 basket Stack을 이용하여 인형이 제거되는 갯수를 센다. #include // Level1_ 크레인 인형뽑기 게임 [스택] #include #include #include using namespace std; int solution(vector board, vector moves) { int answer = 0; stack doll[board.size()]; stack basket; for(int i = board.size()-1; i>=0; i--){ for(int j =0; j