https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 문제조건 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있다. 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 숫자를 최대로 뽑는 경우, 뽑는 숫자들을 출력하라. 접근방법 모든 경우의 수를 따져서 비교해줄려고 DF..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 문제조건 부모 자식들간의 관계가 주어졌을때, 계산하고자 하는 두사람의 촌수를 구해라 접근방법 트리 모양 구조를 탐색하는 그래프 탐색 방법으로 접근했다. 근데 촌수 이므로 cycle이 생길 일은 없다. 따라서 각 노드를 양방향 연결해주고 DFS로 탐색해줬다. 아버지의 형제들과 나와의 관계는 3촌으로 분류할 수 있는데, 이를 계산하는 방식은 나 → 아버지(1촌) → 할아버지(2촌)..

https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 문제조건 시작점, 시작방향, 세대가 주어진다. K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다. 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다. 접근방법 같은 모양이 계속해서 반복해서 추가되는 것을보고, DP아니면, 재귀의 형식으로 풀 수 있지 ..

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 문제조건 톱니바퀴 4개, S극(1), N극(0) 존재 각 톱니바퀴가 맞닿아있는 부분이 극이 다르면 다른 방향으로 회전, 같으면 맞닿아있는 톱니바퀴는 회전X 12시방향부터 시계방향순서대로 8개의 톱니에 S, N 주어짐 돌리는 과정을 모두 수행한뒤, 최종적인 톱니바퀴 상태에서 4개의 12시방향에 있는 S들의 합 문제 파악하는데 30분 정도 걸린거같다. 역시나 문제는 복잡하고 풀이 방법은 쉽겠지,,..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제조건 n명의 사람을 각각 n/2 명씩 두팀으로 나눈다. 한 팀의 능력치는 (i, j) 가 같은 팀이라면 map[i][j] + map[j][i]로 나타내고, 같은 팀의 사람들의 능력치를 모두더한다. 두 팀의 능력치 차이의 최솟값은? 접근방법 보자마자 입력값도 작고, 최솟값을 구하기 위해 모든 경우의 수를 Brute Force로 탐색하면 되는 거 아닌가? 생각이 들었고, DFS로 모든 경우의 수에 대해서 탐색했다. 너..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 문제조건 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우, 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌아간다. 바라보는 방향의 뒤쪽 칸이 벽이라 후진할 수 없다면 작동을 멈춘다. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우, 반..

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 문제조건 n x n 크기의 대나무숲 어디든지 판다를 풀어놓을수 있다. 판다는 대나무를 다먹으면 상, 하, 좌, 우 중 한지역으로 이동한다. 이동하는 칸의 대나무가 원래있던 칸의 대나무 수보다 많아야 이동한다. 가장 많이 이동하는 경우의 이동수는? 접근방법 문제를 보자마자 생각이 들었다. '아 그냥 완전탐색돌려서 최댓값 갱신해서 찾자' 내가 좋아하는 DFS 알고리즘으로 모든 경우의 수를 ..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제조건 퇴사 전까지 상담을해서 얻을수 있는 최대 수익을 구하라 단순히 구현 + dp 문제였다. dp[i] : i일까지의 상담중에서 최대 수익 값 완전탐색을 진행하면서 상담에 걸리는 일수가 퇴사 전일때, 구하고자 하는 일자의 수익과, 지금까지의 수익 + 구하고자 하는 일자까지 상담하는 수익을 비교해서 최댓값을 갱신시켜줬다. 소스코드 #include #include using namespace std; int n, t[16], p[16], dp[16]; int main(){ cin >> n; for (int i = 0; i < n; i..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제조건 연결된 4개의 정사각형 블록으로 모양을 만든다. 만들어진 모양을 종이위에 올렸을때, 4개의 숫자의 합의 최댓값은? 접근방법 완전탐색을 위해서 brute force로 접근해봤다. 그래서 전체 map을 돌면서 DFS를 수행할 수 있도록 구현했다. #include using namespace std; int n, m, map[501][501], visited[501][501]; int dy[]..

https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 문제조건 n개의 시험장 각 시험장의 응시자 수(a) 총감독관이 감시할수 있는 수(b), 부감독관이 감시할수 있는 수(c) 총감독관은 시험장마다 오직 1명만 가능 너무 쉽게 생각했는데, 처음부터 틀려버렸다. 예외 조건이라고는 총감독관 혼자서 응시자를 모두 감시할 수있을경우에 대한 로직만 처리하면 될 줄 알았는데, 뭐가 문제인지 몰랐다. 생각해..