문제 https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 방법 문제에 설명되어있는 것처럼 i번 위치와 j번 위치를 바꾸는 연산을 K번 했을 때 나오는 수들의 최댓값을 구하면 된다. 헷갈릴 수 있는데, 탐색 과정 중의 최댓값을 구하는 게 아니라 탐색을 K번한 후의 최댓값을 구하는 것이다. 예를 들면 예제 입력2의 132 3에서 연산을 2번 했을 때의 수는 132, 213, 321이고 이 중 최댓값은 321이지만 연산을 3번 했을 때는 123, 231, 312로 최댓값은 312가 나온다. 그리고 132->123 , ..
알고리즘
문제 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 풀이 방법 [i, j) 부분 구간의 합이 M으로 나누어 떨어지는 i, j 쌍의 개수를 구하는 문제이다. 배열의 크기 N과 나누는 수 M이 큰 숫자이기 때문에 모든 경우를 계산해보는 방법은 불가능하다. 때문에 배열을 입력 받을 때 부분 합을 미리 계산해놓는다. PrefixSum[j] - PrefixSum[i] % M = 0이 만족하면 Prefix..
문제 https://www.acmicpc.net/problem/2001 2001번: 보석 줍기 첫째 줄에 n, m, K가 주어진다. 다음 K개의 줄에는 보석이 있는 섬의 번호가 주어진다. 다음 m개의 줄에는 각 다리에 대한 정보를 나타내는 세 자연수 a, b, c(1 ≤ c ≤ 100)가 주어진다. 이는 a번 섬과 www.acmicpc.net 풀이 방법 1194번 달이 차오른다, 가자와 비슷한 문제이다. 이 문제에서는 열쇠를 갖고 이동하는 것이 아니라 보석을 줍고 이동하며, 시작점으로 돌아왔을때 보석의 최대 개수를 출력해야한다. 1194번과 유사하게 보석이 최대 14개이므로 보유한 보석을 최대16,384 (1
문제 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 풀이 방법 2206번 벽 부수고 이동하기와 비슷한 문제이다. 이 문제에서는 벽을 부수는 것이 아니라 열쇠로 이동하면 열쇠를 획득하여 해당하는 문을 열 수 있는 것이 특징이다. 따라서 큐에 좌표와 갖고 있는 키 상태를 넣어줘야 하며, 방문도 마찬가지로 키를 갖고있는 상태에서 방문한 좌표를 체크해줘야한다. (3차원 공간) 키를 갖고 있는 것을 어떻게 표현해야할지가 ..
