https://www.acmicpc.net/problem/1473 1473번: 미로 탈출 세준이는 직사각형 모양의 미로에 갇혔다. 미로 안에는 1*1크기의 작은 방이 있다. 정사각형 모양의 각 방은 네 개의 면이 있는데, 이 네 개의 면에는 문이 있을수도 있고, 없을수도 있다. 각 방은 www.acmicpc.net int discovered[1

https://www.acmicpc.net/problem/13209 13209번: 검역소 3번 도시와 5번 도시를 잇는 도로와 4번 도시와 3번 도시를 잇는 도로에 검역소를 설치하면 치료제를 11 인분만 비축해도 된다. 1번 도시에 전염병이 발생할 경우 1번 도시와 3번 도시의 10명의 사 www.acmicpc.net 이분 탐색을 이용하여 트리의 각 그룹들을 mid명 이하로 만들 수 있는지 체크하는 방법으로 문제를 해결했다. 체크하는 방법은 트리를 리프 노드에서부터 올라가면서 확인해 가며 그룹을 만들어 가는데 그룹의 인원이 가능한 최대 인원을 넘으면 최적으로 가능한 부분만 남기고 나머지는 검역소로 간선을 자르는 방법으로 나아갔다. 자른 횟수가 자를 수 있는 횟수를 넘었는지 안 넘었는지 확인하는 방식으로 ..

https://www.acmicpc.net/problem/20549 20549번: 인덕이의 고민 오리를 좋아하는 인덕이는 오리를 바라보며 마음의 안식을 얻는다. 오리는 N×N의 정사각형 모양으로 이루어진 인경호에서 유유자적하게 헤엄을 친다. 인경호는 1×1 크기의 칸으로 나누어져 있 www.acmicpc.net [먹은 음식 상황][행][열] = 최소비용을 저장하여 다익스트라를 구현해 문제를 해결했다 코드 #include #include #include #include #include #include using namespace std; int n; int a, b, c; int m; vector board(50, vector(50, -1)); int a_dxdy[8][2] = { {-1,-2},{-2,-..

https://www.acmicpc.net/problem/17528 17528번: Two Machines 스케줄링 최적화 회사인 SOPT 에 완료해야 할 n개의 작업 t1, t2, ..., tn 이 있다. SOPT 회사는 두 대의 머신 A 와 B 를 보유하고 있다. 각 작업 ti를 완료하기 위해 SOPT 는 머신 A 와 B 둘 중에 오직 하나 www.acmicpc.net cache[62501][250]; 에 [A기계에 쌓여있는 시간][해당 인덱스] = B기계에 쌓여있는 시간을 저장하여 bottom-up 방식으로 B기계에 쌓여있는 시간을 최소로 만드는 설계를 하여 값을 채운 뒤, 마지막 인덱스에서 A기계에 쌓여있는 시간과 B기계에 쌓여있는 시간을 비교하는 방식으로 문제를 해결했다. 코드 #include #..

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net cache[16][(1

https://www.acmicpc.net/problem/14554 14554번: The Other Way 첫째 줄에는 $N$, $M$, $S$, $E$가 하나의 공백으로 구분되어 들어온다. ($2 \le N \le 100000$, $N-1 \le M \le 300000$, $1 \le S, E \le N$, $S \neq E$) 그 후 $M$개의 줄에는 $A$, $B$, $C$가 하나의 공백으로 구분 되어 들어 www.acmicpc.net vector short_cnt(100001, 0)에 [위치] = 해당 위치로 최단경로로 올 수 있는 개수를 저장하여, 해당 위치가 지금까지 구한 최단경로와 같은 비용의 길일 때 지금 경로에서 오는 경로의 개수를 추가하여 문제를 해결했다. 코드 #include #inc..