https://www.acmicpc.net/problem/12014 12014번: 주식 입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에 케이스의 개수 T(2 ≤ T ≤ 100)가 주어지고, 이후 차례로 T 개 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에 두 www.acmicpc.net 가장 긴 증가하는 부분 수열(n log n)을 찾아서 그 길이가 k이상인지 확인하는 방법을 통해 문제를 해결했다. 코드 #include #include #include #include using namespace std; int t; int n, k; vector stock; vector check; vector::iterator it; void init() { stock.clear(); ..

https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 확인할 구슬을 왼쪽 저울에 두었다고 생각하고, cache[확인하는 추의 인덱스][왼쪽 저울 무게와 오른쪽 저울 무게의 차이]인 상황일 때, 양쪽의 차이가 0이 될 수 있는지를 저장하여 다이나믹 프로그래밍을 통해 문제를 해결했다. 코드 #include #include #include #include #include using namespace std; int n; vector choo; int che..

https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net bfs(너비 우선 탐색)을 이용해 문제를 해결하는데, 이때 벽이 어디까지 내려왔는지 확인해야 하므로, bfs를 확인하는 discovered에 위치뿐만이 아니라, 벽들이 얼마큼 내려온 상태까지 확인하여, discovered[행][열][현재 벽들이 얼마큼 내려왔는지(depth)] = (확인한적 없을 때:0, 확인한적 있을 때:1)를 저장하여 문제를 해결했다. 코드 #include #incl..

https://www.acmicpc.net/problem/7573 7573번: 고기잡이 한국인의 식단에서 생선은 매우 중요한 단백질 공급원이다. 반면, 지구 온난화로 인한 바닷물의 온도 상승, 그리고 지금까지 마구잡이로 물고기를 잡은 결과로 점점 우리나라의 바다에서 물고 www.acmicpc.net 각 물고기를 기준으로, 해당 물고기가 그물에 걸리는 모든 경우의 수를 확인하여, 해당 경우에서 총 물고기가 몇 마리 걸리는지 확인하여, 물고기가 가장 많이 걸리는 최댓값을 구해서 문제를 해결했다. 코드 #include #include #include using namespace std; int n, l, m; vector fish; int main() { cin.tie(NULL); ios_base::sync_..

https://www.acmicpc.net/problem/23083 23083번: 꿀벌 승연이 첫째 줄에 \(N\), \(M\)이 공백으로 구분되어 주어진다. 다음 줄에는 구멍 칸의 개수 \(K\)가 주어진다. 이어서 \(K\)개 줄에 구멍 칸의 정보 \(x_i\), \(y_i\)가 공백으로 구분되어 주어진다. 이는 \(i\)번째 www.acmicpc.net 다이나믹 프로그래밍을 이용해 cache[x][y]에 (x, y)에서 (n, m) 위치로 가는 경우의 수를 저장해서 문제를 해결했다. 코드 #include #include #include using namespace std; int n, m; int k; int hole[1005][1005]; vector cache(1005, vector(1005, ..

https://www.acmicpc.net/problem/27651 27651번: 벌레컷 크기 $N$의 $1$차원 양의 정수 배열로 이루어진 자벌레가 있다. 자벌레는 곤충이기 때문에 머리, 가슴, 배로 부위를 구분할 수 있다. 각 부위는 배열상에서 연속하는 구간으로 나타낼 수 있으며 배 www.acmicpc.net 무게의 조건이 가슴 > 배 > 머리 이므로, 이를 가슴 > 머리, 배 > 머리, 가슴 > 배로 나눠서 생각했다. 전체적인 풀이 방법은, 1~x까지 머리 부위, x+1~y까지 가슴 부위, y+1~n까지 배 부위로 나눠서 모든 x를 확인해 보면서, 해당 x에 대해, 가슴 > 머리, 배 > 머리 를 만족하는 y가 될 수 있는 후보 범위 (range_y_left~range_y_right)를 구했고, ..