https://www.acmicpc.net/problem/18290 18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net 간단한 백트래킹 문제였습니다. 격자판을 백트래킹으로 탐색하면서 가능한 위치의 점이 여태 지나온 점들의 인접한 점과 일치하는 점인지 확인하면서 계산하면 됩니다. 그리고 가능한 점이면 해당 점의 인접한 점 또한 체크리스트에 포함시키면서 진행하면 됩니다. 코드는 다음과 같습니다. #include #include #include using namespace std; int n, m, k; in..
https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 0 ~ n-1 번 사람을 노드로 봤을 때 연속으로 노드가 5개 이어질 수 있느냐 없느냐의 문제입니다. dfs를 이용해서 해당 노드의 깊이가 4가 된 순간이 5개를 연속으로 탐색한 경우이므로 해당 경우가 발생하면 정답입니다. 코드는 다음과 같습니다. #include #include #include #include using namespace std; // 각 숫자 node로 보고 // 시작 노드로부터 dfs depth 4면 정답 // 5개 연결된 거랑 동일 int n, m; vector vec[2001]..
https://www.acmicpc.net/problem/2836 2836번: 수상 택시 상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 0번부터 M번까지 강을 따라서 번호가 매겨져 있고, 인접한 집 사이의 거리는 모두 1 킬로미터이다. www.acmicpc.net 수상 택시로 사람들을 태워다니면서 가는 최소 거리를 구하는 문제입니다. 태우는 사람에 대한 조건은 따로 없으니 순방향으로 가는 사람은 가는 길에 내려준다고 생각하면 총 M 만큼 이동합니다. 역방향으로 가는 사람은 스위핑 알고리즘을 이용한 선분 길이 구하는 것과 동일하게 계산하면서 x 2 만큼 길이를 구하면 됩니다. (역방향이므로 갔다가 다시 원래 방향으로 가야 함) 코드는 아래와 같습니다. #i..
https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 제한 시간을 10초나 주길래 별 생각 없이 풀다가 낭패를 본 문제입니다. 처음 생각했던 방안은 놓일 수 있는 모든 위치에 대해서 하나씩 놓아보면서 현재 최대값 결과인 result >= 현재까지 놓인 개수 res + 뒤에 남은 1인 칸 이면 탐색을 종료하도록 구성하였습니다. 하지만 이렇게 구성하니 시간초과가 떴고, 해당 방법을 이용하면 복잡도가 O(2^(N*N)) 임을 알게 되었습니다. 이를 해결하기 위해 ..
https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net 노란색 칸은 배양액을 뿌릴 수 있는 위치, 흰색은 배양액을 뿌릴 수는 없지만 퍼질 수 있는 위치, 파란색은 호수로 이루어져 있습니다. 이 때 빨간색 배양액과 초록색 배양액을 모두 뿌렸을 때 (겹치게 뿌리면 안 됨) 동시에 만나는 지점에서 꽃이 피고, 이 때 꽃의 최대 개수를 구하는 문제입니다. 전체 칸이 50x50, 배양액 개수가 최대 5..