문제 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 풀이 방법 (0,0)부터 시작해서 (10,10)까지 종이에 1이 적혀있으면 큰 색종이부터 작은 색종이까지 붙일 수 있는 종이를 다 붙혔다 뗐다하면서(백트래킹) 깊이 우선 탐색을 한다. 2580번 스도쿠와 비슷할 수도 있는 문제. 코드 #include #include #include using namespace std; int answer = 0x6FFFFFFF; void dfs(ve..
프로그래밍/Algorithm
문제 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
