1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net - 문제 설명 N, K가 주어짐 N줄에 걸쳐 보석의 정보(무게 M, 가격 V)가 주어짐 K줄에 걸쳐 가방의 크기 (= 넣을 수 있는 보석의 최대 무게)가 주어짐 각 가방에는 보석을 최대 1개만 넣을 수 있음 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하라 - 첫 접근방법 (시간초과) 가장 가치가 큰 보석부터 확인 (크기가 작은순으로 정렬 후 가치순으로 다시 정렬) 가치가 큰 보석을 최대한 크기가 작은..

5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 알고리즘 공부법으로 어떤 유형을 끝까지 파고 난 후 다른 유형으로 넘어가는 것과 모든 유형을 조금씩 공부하는 방법 중 어떤 것이 더 도움이 될까 고민이었다. 여러 의견과 조언을 구한 후 한 유형을 쭉 파보는 방법으로 공부하기로 결론지었다. 백준 BFS 문제인 백조의 호수를 풀수 있을 때까지는 BFS에 집중해 공부를 해보려 한다. - 문제 설명 상근이가 불이난 건물안에 갇혀있다. 불이 번지기 전에 빠르게 건물밖으로 탈출해야한다. 빈공간은 '.', 벽은 '#', 상근이 위치는 ..

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net - 문제 설명 수빈이가 동생과 숨바꼭질을 한다. 수빈이는 동생을 찾기위해 순간이동, 앞으로 한칸이동, 뒤로 한칸이동이 가능한다. 순간이동은 0초, 앞뒤로 한칸이동은 1초가 걸린다. 수빈이가 동생을 찾을 수 있는 가장 빠른 시간은 몇초후인가? - 접근방법 BFS방식으로 순간이동 하는경우, 앞뒤로 이동하는 경우를 모두 탐색하자 순간이동은 뒤로는 할수 없다. 만약 수빈이가 동생보다 앞에있다면 뒤로가기로만 찾을 수 있으므로 수빈이와 동생..

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net - 문제 설명 N * M 배열로 북극의 빙산이 주어진다. 빙산이 존재하는 칸에는 양의 정수가 주어지고, 바다인 칸에는 0이 저장된다. 빙산은 바닷물에 닿아있으면 빨리녹아 빙산에 저장된 숫자는 1년마다 빙산 주변의 바다 칸 개수만큼 숫자가 줄어든다. 빙산이 두 덩이리 이상으로 분리되는 최초의 시간(년)을 구한다. 빙산이 마지막까지 두 덩어리 이상으로 나눠지지 않는 경우 0을 출력한다. 초기 빙산 1년 후 빙산 - 접근방법 빙산을 먼저 녹인 후 BFS를 이용해..

1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net - 문제 설명 TV를 보다 채널을 돌리려고하는데 고장난 버튼이 있다. 고장나지 않은 버튼과 +, - 버튼을 눌러 보고싶은 채널로 이동한다. 초기에 채널은 100번채널이다. 100번에서 +, - 버튼으로 이동한 횟수와 숫자 버튼으로 이동한 후 +, - 로 다시 이동한 경우 중 최솟값을 찾는다. - 입출력 예시 - 처음 접근방법 최초에 누르려는 버튼의 길이만큼 버튼을 눌러 목표 채널과 가장 가까운채널을 찾는다. 그래서 고장나지 않은 버튼만 들어있는 ..

2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net - 문제 설명 2차원 배열 모눈종이 위에 치즈가 존재한다. 어떤 칸에 존재하는 치즈가 2칸이상 치즈가 아닌 칸 (외부 공기)로 접촉하여 있다면 그 칸의 치즈는 1시간 후 녹아 사라진다. 치즈 속에 존재하는 빈칸(치즈 속 공기)는 외부공기에 접촉하지 않았다고 생각한다. 위 그림을 보면 외부 공기와 2칸 이상 접촉한 치즈는 사라졌고 내부공기와 접촉한 치즈는 그대로 존재한다. - 접근방법 또다시 BFS로 풀어야겠다는 생각이 들었다. 내부 공기와 외부공기는..