2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 1. 문제 아래 그림과 같이 c로 표시된 부분은 녹아서 빈 칸이 되고, 빨간색으로 표시한 치즈의 가장자리가 새로운 'c'가 된다. 3시간 후 모든 치즈가 녹아 없어졌고, 모두 녹기 1시간 전 치즈의 개수는 에서 확인할 수 있듯 5개이다. 그렇기 때문에 첫 줄에는 3, 두 번째 줄에는 5를 출력한다. 2. 구현 아이디어 이번 문제에서는 치즈 안에 있는 구멍(위 그림 속 빨간 영역)과 치즈 밖의 공간을 어떻게 구분할지가 핵심 포인트이다. 치즈 안의 공간을 단순히 0이라고 하고 인접한 ..

2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 1. 문제 2. 구현 아이디어 자두는 최대 30번 움직이고, 1번 나무 또는 2번 나무로 이동하므로(0, 1) 전체 경우의 수는 2^30가지이다. 그렇기 때문에 완전탐색으로 푸는 것은 불가능하다. (i-1)초일 때 최대 자두 갯수를 알면, 이동할지 말지 여부에 따라 i초일 때의 최대 자두 갯수를 알 수 있기 때문에 DP로 문제를 풀 수 있다. 문제에서 3가지 상태(이동 횟수, 자두의 위치, 흐른 시간)이 있기 때문에 3차원 배열로 각 상태에 따른 자두의 최대 개수를 DP..

3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 1. 문제 예제 1을 그림으로 표현하면 다음과 같다. 개똥벌레가 높이가 3.5, 5.5, 6.5인 지점을 지날 때 파괴해야 하는 장애물이 2개로 이 때가 최소가 된다. 2. 구현 아이디어 석순과 종유석을 따로 저장한다 종유석은 (높이)-(장애물의 길이)로 저장한다 반복문을 통해 모든 지점에 대해 각 위치에 대해 파괴해야 할 장애물의 위치를 센다 편의상 0.5, 1.5처럼 X.5 지점이라고 생각하자 이분 탐색을 사용하여 나는 지점(target)의 위치를 확인하고, 그..

1. 문제 2. 구현 아이디어 - 맞았습니다!! 구역의 개수를 세면 되는 그래프 문제이다. BFS와 DFS 둘 다 가능하기 때문에 편한대로 사용하면 된다. 나는 BFS로 문제를 풀었다. 주의 ⚠️ 나는 평소에 행을 x, 열을 y로 푸는데 배추의 위치가 (열, 행) 순으로 들어오기 때문에 순서가 바뀌지 않도록 주의하여야 한다! 2중 반복문으로 배추밭 배열을 돌면서 현재 위치가 1이고 아직 방문하지 않았다면 해당 좌표를 시작점으로 BFS를 돈다. BFS를 돈 뒤, 배추흰지렁이의 개수(ret)를 +1해준다. 일반적인 BFS 문제이고, 자세한 설명은 코드에 주석으로 달겠다. #include using namespace std; int t; int m, n, k; int x, y; int arr[54][54]; ..

17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 틀렸습니다, 시간 초과 무식하게 풀 경우 최대 연산 횟수는 1,000,000 + 999,999 + ... + 1 = 500,000,500,000으로 5000억번 가량이 되므로 다른 방법을 찾아야 한다. 요즘 코테 공부하면서 큰돌 선생님 강의를 듣고 있는데 문제를 접근할 때 완전탐색 > DP > 그리디 순서로 생각해보라고 했다. 완전탐색이 안되기 때문에 DP로 문제를 풀어보려고 했다. dp[i]에 i번째 원소의 오큰수를 담는다고 했을..

2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 1️⃣ 문제 설명 2️⃣ 예제 설명 예제 1에서 1~5 구간에서는 겹치는 선이 하나로 인식되어 길이가 4인 선분이 되고, 6~7 구간이 길이가 1인 선분이 되어 그은 선의 총 길이는 4+1=5가 된다. 3️⃣ 구현 아이디어 - 틀렸습니다 처음에 문제를 봤을 때 최근에 풀었던 회의실 배정과 비슷해보여 끝나는 지점을 기준으로 정렬하여 문제를 풀어보려고 했다. N의 최댓값이 1,000,000이고 x와 y의 최솟값과 최댓값이 -1,000..