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} 등이 있고, 원소가 하나일 때도 증가하는 부분 수열에 포함된다. 이번 포스트에서 소개할 가장 긴 증가하는 부분 수열은 그 중에서도 가장 길이가 긴 것을 의미한다. 가장..

2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 1. 문제 설명 예제 1에서 1번부터 5번 회원의 점수는 각각 3점, 2점, 2점, 2점, 3점이다. 그러므로 가장 작은 점수는 2점이 되고, 점수가 2점인 2, 3, 4번 회원 총 3명이 회장 후보가 되는 것이다. 2. 구현 아이디어 1 - 틀렸습니다. 1. 현재 노드에서 가장 거리가 먼 노드까지의 거리가 해당 회원의 점수가 된다. 2. 모든 회원의 점수를 배열에 저장하고, 배열의 최솟값(=score)을 찾는다. 3. 값이 score인 원소의 index를 ca..