1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 맞았습니다!! 힌트를 통해 직관적으로 BFS를 사용해서 영역의 최댓값을 구하면 되겠다고 생각할 수 있었다! 주어진 입력의 크기도 크지 않고, 특별한 예외 조건이 없어 일반적인 BFS 로직을 사용하여 문제를 해결할 수 있었다! BFS를 구현해야 하므로 큐를 사용해주었다. 예제 입력 1과 힌트에 나온 그림을 비교했을 때 왼쪽 상단이 (1, 1)이기 때문에 좌표가 0부터가 아닌 1부터..

15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 N의 최댓값이 3,000,000이고 k의 범위가 3,000이므로 시간 초과에 주의하여야 한다. 먼저 k개를 넣어두고, 앞에 있는 초밥을 빼고 새로운 초밥을 넣는다 → 덱 자료구조를 활용 key를 초밥의 종류, value를 초밥의 갯수로 저장하여 초밥의 존재 여부와 갯수를 계산하자. #include using namespace std; int sushi[3001] = {0}; // 초밥..

18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 맞았습니다 !! 문제에서 계속 언급한 것처럼 '최단 거리'를 구하는 문제이기 때문에 다익스트라 알고리즘 or 플로이드-와샬 알고리즘을 사용해야겠다고 생각할 수 있었다. 출발 도시 번호가 주어지고 특정 노드로부터 다른 노드의 최단 거리를 구해야 함 입력으로 주어지는 n, m, k가 각각 30만, 100만, 30만으로 작지 않음 1번만으로도 다익스트라 ..

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 틀렸습니다 문제를 풀면서 덩어리가 몇 개인지 구해야 한다는 점에서 BFS/DFS 문제임을 알 수 있었다. 위 사진에서 높이가 2인 빙산이 녹으면서 0이 되고, 높이가 4인 빙산은 2가 되었다. 모든 빙산은 다 같이 줄어드는 것이기 때문에 높이가 4인 빙산 주변의 0인 칸을 셀 때 2→0인 빙산이 포함되지 않도록 주의해야 한다 !! 문제를 풀기 위해 아래와 같은 풀이 과정을 떠올렸다. 1. 입력을 받으면서 빙산의 좌..

2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 1 - 맞았습니다 !! 연속으로 3잔을 모두 마실 수 없다는 점을 유의해서 풀면 되는 문제이다. 이제까지 마신 최대 포도주의 양을 계산하고, 연속으로 마신 잔의 수에 따라 현재 위치에 있는 포도주를 마실지 말지 결정하는 것이 DP 문제에서 나오는 자주 나오는 로직이여서 DP를 사용하여 문제를 풀 수 있다고 생각할 수 있었다. 각 위치의 포도주의 양을 담은 배열을 arr라고 하고 dp[i] = 0~i번째 위치에 있는 포도주까지 고..

1. 부분 수열과 증가하는 부분 수열이란? 부분 수열 부분 수열이란 주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열을 의미한다. 만약 { 3, 2, 5, 2, 3, 1, 4 } 라는 수열이 있다면 {3}, {2}, {2, 5}, {3, 5, 3, 1} 등이 해당 수열의 부분 수열이 되며, 수열 자체도 자기 자신의 부분 수열에 포함된다. 증가하는 부분 수열 증가하는 부분 수열은 부분 수열들 중에서도 그 수가 오름차순으로 증가하는 부분 수열을 의미한다. 위에 있던 수열의 증가하는 부분 수열은 {2, 5}, {2, 3, 4} 등이 있고, 원소가 하나일 때도 증가하는 부분 수열에 포함된다. 이번 포스트에서 소개할 가장 긴 증가하는 부분 수열은 그 중에서도 가장 길이가 긴 것을 의미한다. 가장..