문제 한 변의 길이가 N인 정사각형 모양의 평면에 진딧물 집과 개미 집이 있다. 개미 집은 고유의 영역 범위 안의 모든 진딧물에게서 수액을 수집한다. 이 수액이 없으면, 개미 집은 부족한 식량으로 제거된다. 길이가 4인 정사각형 평면을 1*1 크기의 작은 정사각형으로 나누면 아래와 같은 그림으로 표현할 수 있다. 위와 같은 상태로 arr[i][j] 값들이 주어진다. arr[i][j]의 값은 0, 1, 2 중 하나이며, 1 은 개미 집이고, 2는 진딧물이다. 아래 조건에 따라 개미 집은 제거된다. ●arr[i][j]이 개미 집 이라면, M칸 안에 진딧물이 없을 때 제거된다. ●이때 거리를 측정하는 방법은 상하좌우 인접한 칸으로 한 번 이동할 때 마다 1칸 움직인 것으로 한다. 위의 규칙에 따라 개미 집이 ..

DP유형의 문제라는 것을 파악하고 점화식을 찾기 위해 하루 꼬박 투자했지만 결국 점화식을 구하지 못하고 해설을 봤다. 문제 난이도가 너무 높다고 느껴졌고 해설을 보고서도 이해하는데 굉장히 오래걸렸다. 해설에 파이썬 코드를 c++언어로 아래와 같이 작성했다. #include #include using namespace std; int n; deque dp; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; dp.push_back(0); dp.push_back(0); dp.push_back(1); for (int i = 3; i

문제 구름이는 구름카페를 운영하는 사장님이다. 구름카페에는 아래 그림처럼 한 줄에 3개의 테이블이 있고, 이러한 줄이 총 N 줄 배치되어 있다. 기존에는 모든 테이블에 동시에 사람들이 앉을 수 있었다. 하지만 사람들 사이에서 소음으로 자주 다툼이 발생하자, 구름이는 테이블 간 거리두기를 시행해서 일부 테이블에서만 앉아서 커피를 마시거나 작업을 할 수 있도록 하려고 한다. 테이블 간 거리두기를 시행하게 되면 어떤 사람이 앉아있는 자리에서 앞뒤와 양옆으로 인접한 테이블에는 동시에 사람들이 앉을 수 없게 된다. 구름이는 거리두기 방식에 따라, 사람들이 앉을 수 있는 테이블에 스티커를 붙이기로 했다. 구름이는 충분히 많은 스티커를 가지고 있기 때문에 붙일 수 있는 스티커의 개수에는 제한이 없으며, 스티커를 하나..

문제 가을이 되면서, 단풍나무가 물들기 시작하려고 한다. 구름공원에서는 크기가 N*N인 땅에 단풍나무를 많이 심어두었다. 구름공원은 땅을 효율적으로 관리하기 위해, 땅을 1*1 크기의 작은 구역 단위로 나눈 뒤 해당 구역에 심어진 나무들을 묶어서 관리하고 있다. N=4일 때 공원은 아래와 같이 16개의 작은 구역으로 나눠지게 되고, 각 구역의 이름은 아래와 같다. 구름공원의 관리자 구름이는 모든 단풍나무가 물드는 시점을 파악하려고 한다. 단풍나무가 물드는 규칙은 아래와 같다. ●arr[i][j]에는 해당 구역에 아직 물들지 않은 단풍나무의 수가 적혀 있다. ●arr[i][j]의 값이의 값이 0이면, 해당 구역의 모든 단풍나무가 물들었다는 것을 의미한다. ●arr[i][j]의 값은 매일 밤마다 상하좌우로 ..

주어진 조건을 얼마나 정확하게 이해하는 것이 중요한 문제였다. 먼저, 문제를 읽고 아래와 같이 명령어에 따라 선택해야 하는 수행 동작을 정리하였다. 1.deposit : k금액 입금 후 결제 대기 목록에 따라 결제 진행 2.pay : 계좌에 k이상 금액이 있는 경우 k만큼 결제 3.reservation 3-1)계좌에 k이상 금액이 있는 경우 k만큼 결제 3-2)계좌에 금액이 부족한 경우 결제 대기 목록에 추가(선입선출을 위해 큐를 사용) 구현 코드는 아래와 같다. #include #include using namespace std; int n, m, cost; string command; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)..

문제 구름이는 도시의 물을 관리하는 관리자이다. 현재 도시에는 물을 잠시 보관하는 물탱크와 물탱크끼리 연결하는 수로가 아래의 조건으로 설치되어 있다. ●N개의 물탱크와 N개의 수로가 있다. ●물탱크는 1번부터 N번까지 있다. ●수로가 연결된 물탱크는 양 쪽으로 물이 흐른다. ●서로 다른 두 물탱크를 잇는 수로는 최대 하나이다. ●물탱크에서 연결된 물탱크는 항상 다른 물탱크이다. ●모든 물탱크는 연결되어 있다. 즉, 어떤 물탱크에서 임의의 다른 물탱크로 항상 물이 흐를 수 있다. 도시의 물은 흐르지 않으면 녹조류가 생기기 때문에, 항상 물이 순환하도록 유지하는 것이 중요하다. 하지만, 구름이는 순환하는 물이 항상 모든 물탱크를 지나지 않는다는 점을 확인했다. 구름이는 현재 상태의 수로를 확인하고, 순환하는..

1.DFS 문제를 읽고 바로 DFS로 해결할 수 있을 거라 판단하여 바로 구현을 시작했다. #include #include using namespace std; int n, m, k, u, v, visited[1001], flag; vector bridge[1001]; void dfs(int cur, int move) { if (move > k) return; if (visited[cur]) return; visited[cur] = 1; if (cur == n) { flag = 1; return; } for (auto& n : bridge[cur]) { if (flag) return; dfs(n, move + 1); visited[n] = 0; } return; } int main() { ios::syn..

문제 10년 전, 구름이가 처음으로 구매했던 휴대폰은 폴더 폰이다. 폴더 폰의 자판은 최근의 휴대폰의 입력 방식과는 차이가 있다. 폴더 폰의 자판 형식은 아래와 같다. 9개의 입력 버튼으로 이루어져 있으며, 각 버튼의 첫 번째 숫자로 버튼을 부를 수 있다. 한 번 버튼을 누르면 숫자가 입력이 되고, 여러 번 누르면 자판에 보이는 문자들로 순서대로 바뀐다. 예를 들면 [버튼 5]를 한 번 누르면 5가 입력이 되지만, [버튼 5]를 세 번 누르면 k가 입력된다. 또 [버튼 5]를 5번 이상 누르게 되면 다시 처음 숫자가 입력된다. [버튼 7]이나 [버튼 1]은 6번 이상일 때 동일하게 된다. 10년 전 구름이가 구매한 폴더 폰을 오랜만에 꺼내서 작동을 했더니, 휴대폰이 고장이 났다는 사실을 발견했다. 같은 ..

구름이의 실수로 인해 소개팅을 받지 못하는 커플은 단 한쌍이므로 한쌍을 제외한 모든 사람은 자신의 점수 n에 반대 되는 -n점의 사람을 찾을 수 있다. 처음엔 단순하게 이중 for문으로 0번째 사람부터 n-1번째 사람까지 탐색하며 각자의 짝을 찾고자 하였다. #include #include using namespace std; int n; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; vector people(n); vector check(n, 0); for (int i = 0; i > people[i]; for (int i = 0; i < n -1; i++) { for (int j = ..