https://www.acmicpc.net/problem/10844 풀이 과정dp 파트가 약해서 정리해보고자 한다.문제를 요약해 보자면 ' N자리 수가 있을 때, 인접한 모든 자릿수가 1씩 차이씩 나는 수가 몇 개인지 구하는 것'이다. 여기서 유의해야 할 점은 다음 두 가지를 조심해야 한다. 1) N번째 자릿수의 자릿값이 0인 경우: 다음 자릿수의 자릿값은 1밖에 올 수가 없다.2) N번째 자릿수의 자릿값이 9인 경우: 다음 자릿수의 자릿값은 8밖에 올 수가 없다. 즉 10 다음에 붙을 수 있는 값은 1밖에 없으므로 101이 되는 것이고,만약 19가 온다면 8밖에 올 수 없으므로 198이 되는 것이다.그 외의 값 (2~8)은 각 값보다 -1 또는 +1 인 값을 가질 수 있다. 그럼 자릿값은 0~9를 가질..

https://www.acmicpc.net/problem/17471 풀이과정먼저 문제에 대해서 간단히 설명해보자면 다음과 같이 그래프가 주어졌을 때2가지 구역으로 나눠서, 두 구역의 인구수 차이의 최솟값을 구하는 문제이다. 여기서 유니온 파인드 알고리즘을 생각할 수 있었다. 문제의 조건으로는각 구역은 1개 이상의 지역으로 이루어져야된다고 한다. (1) (2, 3, 4, 5, 6)(2) (1, 3, 4, 5, 6)....(1, 2) (3, 4, 5, 6)(1, 3) (2, 4, 5, 6)(1, 4) (2, 3, 5, 6)...(1, 2, 3) (4, 5, 6)(1, 2, 4) (3, 5, 6) 이런 식으로 2가지 구역이 나눠질 수 있어서지역의 개수 N개에서최소 지역의 개수인 1부터 최대 N / 2개까지 뽑..

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에www.acmicpc.net풀이과정처음에는 단순하게 DFS 재귀 백트래킹을 이용하여 구현했다.하지만, DP를 사용하지 않으면 시간초과가 났다. 괜히 골드3 문제가 아니다.DP와 DFS를 같이 사용해야 하는 새로운 문제 유형이었다.만약 이 그림 (0, 0)에 판다를 냅둔다면, (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 1) 을 통해서 총 5일을 살게 될 것이다. 그럼 dp[0][0] ..

https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 각각의 도시 사이에 이동하는데 필요한 시간이 주어진다. A에서 B로 가는 시간과 B에서 A로 가는 시간은 같다. 또, A와 B www.acmicpc.net 풀이과정 예제 입력으로 플로이드 와샬 알고리즘을 수행한 시간이 입력된다. 그럼에도 불구하고, 플로이드 와샬을 할 때 어느 도시를 거치는 게 더 짧다면 최소 이동시간이 아니므로 이는 불가능한 경우에 해당되며 -1을 출력한다. i에서 j로 가는 경로가 k로 거쳐가는 경우와 같다면 모든 경로를 최소의 도로로 커버해야 하므로 k를 거쳐가는 도로를 선택한다. #include #inclu..

https://www.acmicpc.net/problem/21940 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 풀이과정 #include #include #include using namespace std; int N, M, a, b, t, K, city[201]; int num[201][201]; const int INF = 1e9; void floyd() { for (int k = 1; k N >> M; for (int i = 1; i a >> b >> t; num[a][b] = t; } cin >> K; for (int i = 1; i > city[i..

https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 풀이과정 자신에서 자신으로 갈 수 없으니, i == j 일 때를 제외한 나머지 부분들은 무한대로 초기 설정한다. 그리고 num 배열에 각 정점에서 얻을 수 있는 아이템이 몇 개인지 입력받는다. 플로이드 와샬을 시행했을 때, 결과는 아래 사진처럼 나오게 되는데, 여기서의 숫자들은 각 노드에서 다른 노드를 갈 때 길의 길이가 얼마인지 알려주는 숫자들이다. 수색범위가 m이니까 각 노드에서 갈 때를 비교하여 ..

https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 풀이과정 일단 각 간선의 가중치를 1로 잡았다. 자신의 키가 몇 번째인지 알 수 있으려면, 자신을 제외한 무한대가 아닌 노드들이 N - 1개여야 한다. num[i][j] = 1이라는 것은 i보다 j가 크다는 뜻이고, num[j][i] = 1이라는 것은 i보다 j가 작다는 뜻이다. 이 두 가지 경우 다 i학생의 기준에서 키의 기준을 알 수 있다. 그러므로 num[i][j] != INF 또는 num[j..

https://www.acmicpc.net/problem/2910 2910번: 빈도 정렬 첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000) 둘째 줄에 메시지 수열이 주어진다. www.acmicpc.net 풀이 과정 #include #include #include #include #include using namespace std; map m; map m1; vector v; bool cmp(pair a, pair b) { if (a.first == b.first) return m1[a.second] b.first; } int main() { ios::sync_with_stdio(f..

https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 풀이과정 map의 find 함수를 알게 해 준 문제이다. res를 입력받고 res의 key값을 찾으면 그에 맞는 value를 출력해주면 된다. #include #include #include #include #include using namespace std; int N, M; string adress, passwd, res; int main() { ios::sync..

https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net 풀이과정 처음으로 set을 사용해봤다. map을 사용하지 않고, set을 사용한 이유는 중복되는 값을 삭제해야 되기 때문이다. 이것이 set의 가장 큰 메리트라고 생각한다. 좋은 문제인 것 같다! next_permutation - 현재 나와있는 수열에서 인자로 넘어간 범위에 해당하는 다음 순열을 구한다. - 사전식으로 정렬한다. - 사용 전에 꼭 sort하고 시작해야 한다. #include #include #include #include #include using namespace std; ..