1, 2, 3 더하기 시리즈 1, 2, 3 더하기 1, 2, 3 더하기 2 1, 2, 3 더하기 3 1, 2, 3 더하기 4 1, 2, 3 더하기 5 1, 2, 3 더하기 6 1, 2, 3 더하기 7 1, 2, 3 더하기 8 1, 2, 3 더하기 9 문제 12101번: 1, 2, 3 더하기 2 n을 1, 2, 3의 합으로 나타내는 방법 중에서 사전 순으로 k번째에 오는 것을 출력한다. k번째 오는 식이 없는 경우에는 -1을 출력한다. www.acmicpc.net 문제 풀이 1, 2, 3을 활용하여 N을 구할 수 있는 경우의 수 중 K 번째의 수식을 출력하는 문제이다. 문제의 경우 N의 크기가 크지 않기 때문에 DFS로 백트랙킹하여 문제를 쉽게 풀 수 있다. 재귀 호출을 하면서 구한 수의 합이 N보다 크다..
문제 14238번: 출근 기록 스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다. 이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 www.acmicpc.net 문제 풀이 세 직원 A, B, C가 있다. 회사에는 특별한 룰을 가지고 있어서 하루에 한 명만 출근한다. 각 직원에 따라 출근할 수 있는 규칙이 정해져 있다. A의 경우 매일 출근할 수 있으며, B의 출근한 다음날은 쉬어야 한다. C의 경우 출근한 다음날과 그다음 날 모두 쉬어야 한다는 규칙이 있다. 따라서 dp의 배열을 5차원 배열로 `dp[a][b][c][전전날][전날]`과 같이 기록하여, 중복으로 경우의 수를 탐색하지 않도록 하여야 한다. ..
문제 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 � www.acmicpc.net 문제 풀이 1xN의 미로에는 각 칸에 정수가 적혀있다. 예를 들어 칸에 3이 적혀있다면 현재 위치에서 +1, +2, +3으로 점프할 수 있다. 이때, 최소한으로 점프하여 가장 오른쪽 끝으로 갈 수 있을 경우 점프 횟수를 반환하고 그렇지 않을 경우 -1을 반환하여야 한다. 문제를 풀기 위해서는 BFS를 통해, 현재 위치에서 탐색 가능한 경로를 추가하는 방식을 사용하여 탐색을 진행하면 된다. 만약 BFS로 모든 경우의 수를 탐색하여도 답을 찾지 못..
문제 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net 문제 풀이 정수 하나를 사용하여 연산을 N-1번 적용한다. 적용할 수 있는 연산은 정수가 3으로 나누어 떨어지는 경우 3으로 나누거나, 2를 곱하는 경우가 있다. 문제에 제시된 조건에 따라 DFS를 통하여 구하면 쉽게 문제를 풀 수 있다. DFS로 푸는 것은 다른 문제에서도 많이 다루었고 `서로소`의 성질을 이용하여 3으로 가장 많이 나누어 떨어지는 수부터 정렬하는 방식을 사용하여 푸는 방법이 있다. 만약, DFS로 풀고자 한다면 DFS의 ..
문제 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 문제 풀이 N개의 문제가 주어지고, 각각의 문제에 대한 난이도가 주어진다. 2개 이상의 문제를 선택할 때 모든 문제 난이도의 합은 L보다 크고, R보다 작어야 한다. 또한, 가장 어려운 문제와 가장 쉬운 문제의 난이도 차는 X보다 크거나 같아야 한다. 문제를 풀기 위해서는 DFS를 통해 조합을 구하면 된다. DFS로 조합을 구하는 방법은 N과 M (2) 와 동일한 로직으로 풀면 된다. `itertools.combination`로 구하면 가지치기를 할 수 없어 시간초과가 발생할 것 같다. 코드 from sys import stdin from math import inf d..
문제 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 문제 풀이 뮤탈리스크는 한 번에 3마리의 SCV를 공격할 수 있다. 첫 번째 공격은 9, 두 번째 공격은 3, 세 번째 공격은 1로 체력을 감소시킬 때, 모든 SCV의 체력이 0이 되는 가장 빠른 경우의 공격 횟수를 반환하는 문제이다. DFS를 통해서도 풀 수 있으며 문제를 풀기 위해 BFS를 통해 탐색을 진행하여 문제의 답을 찾았다. (9, 3, 1)로 공격 가능한 패턴을 `permutation`을 활용하여 구한다. BFS를 통해 공격 가능한 패턴만큼 가지를 확장해..
문제 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, �� www.acmicpc.net 문제 풀이 NxM 크기의 보드와 4개의 버튼으로 이루어진 게임에서 버튼을 클릭하여 하나의 동전을 보드 밖으로 보내는 문제이다. 버튼은 상, 하, 좌, 우로 2개의 동전을 동시에 움직이게 한다. 이때 최소로 버튼을 클릭하여 하나의 동전을 보드 밖으로 보내는 경우를 반환하는 문제이다. 이 문제는 앞서 다룬, 구슬 탈출, 구슬 탈출 3와 상당히 유사한 문제이다. 이 문제를 풀 수 있는 로직을 기억한다면 해당 문제 역시 쉽게 풀 수 있다. 문제는 다음 로직과..
문제 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 풀이 크기가 NxN인 도시에서 치킨집과 집이 있을 때, 치킨 집 M개만 선택하고 나머지는 폐업하여야 한다. 이때 도시의 치킨 거리가 가장 작게 되는 경우를 반환하는 문제이다. 문제를 풀기 위해서 아래와 같은 로직을 작성하면 풀 수 있다. 입력된 NxN에서 도시에서 치킨 집과 집의 좌표를 찾는다. DFS를 통해 M개의 치킨집을 선택하고, M개가 선택된 경우 거리를 계산한다. 문제에서 거리를 계산하는 식은 맨하튼 거리이다. 코드 fro..
