CEO

문제 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작거나 같으면서, 가장 큰 값을 구해보� www.acmicpc.net 문제 풀이 A, B의 숫자가 주어질 때 A의 자릿수로 구할 수 있는 순열을 구하여 B보다 작으면서 가장 큰 값을 반환하는 문제이다. `DFS`를 통해 순열을 구하면서, B보다 작은지 확인하고 최대 값을 갱신해 주면 된다. 중간에 가지치기를 해주고 싶어서, 순열의 처음 값이 B의 첫 번째 값보다 크다면 가지를 뻗지 않게 하려고 했는데... 74~75% 정도에서 `틀렸습니다.` 를 출력한다. 가지치지를 하지 않으니 정답을 맞출 수 있었다. 코..

문제 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 문제 풀이 3xN 크기의 벽을 2x1, 1x2 크기의 타일로 채우는 경우를 구하는 문제이다. 문제를 풀기 위해 경우를 찾아보면 다음과 같은 규칙을 찾을 수 있다. N이 홀수인 경우 경우의 수는 0이다. 2x1, 1x2로는 N이 홀수인 경우 채울 수 없다. N = 2 3가지 경우의 수 N = 4 2의 경우의 수 * 3 + 2 N = 6 4의 경우의 수 * 3 + 2의 경우의 수 * 2 + 2 N = 8 6의 경우의 수 * 3 + 4의 경우의 수 * 2 + 2의 경우의 수 * 2 + 2 `dp[N] = dp[N - 2] * 3 + dp[N - 4] * 2 + ... dp..

문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 풀이 계단 아래 시작점부터 꼭대기에 위치한 도착점까지 도착하고자 한다. 각 계단에는 획득할 수 있는 점수가 있으며, 계단을 밟을 수 있는 규칙이 존재한다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안된다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 이 문제는 경우의 수를 뻗어 가능한 경우 중 가장 큰 수를 찾는 문제와 같다. 계단의 개수가 300개 이하이므로 `DFS`로 풀게 될 경우 당연히 시간 초과가..

문제 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 문제 풀이 수식이 주어질 때, 괄호를 추가하여 최대가 되는 수를 반환하는 문제이다. 괄호를 추가하기 위해서는 2가지 방법이 있을 수 있다. 예를 들어 예제 입력 1의 경우 `3 + 8 * 7 - 9 * 2`를 괄호를 추가할 수 있는 경우를 `DFS`로 탐색하는 방법은 다음과 같다. 두수 사이에 하나의 연산자 기호가 있어야 한다. `(3 + 8) * 7 - 9 * 2`와 같이 가장 앞의 연산자부터 우선 처리한다. `3 + (8 * 7) - 9 ..

문제 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 풀이 NxN 격자판에서 파이프를 한쪽 끝 (N, N)으로 이동시키는 방법의 수를 출력하는 문제이다. 파이프는 가로, 세로, 대각선으로 움직일 수 있으며 움직이는 각도는 45도이다. 즉 가로에서 세로, 세로에서 가로는 즉시 변환할 수 없다. 경우의 수를 계산하기 위해 아래와 같이 `DFS`로 풀었다. from sys import stdin def visitable(x, y, direction): if direction == DIA..

문제 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 풀이 N개의 수가 차례대로 입력될 때, 중간 값을 출력하여 반환하는 문제이다. 문제를 풀기 위해서는 `heap`을 left, right로 나누고, left의 루트가 중간값이 되도록 로직을 구현하면 쉽게 해결할 수 있다. left는 최대 힙으로 만들고, right는 최소 힙으로 만들면 pop연산을 활용하기 좋다. 코드 from sys import stdin import heapq if __name__ == '__main__': n = i..

문제 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net 문제 풀이 웜 바이러스가 하나의 네트워크 영역에서 퍼진다. 1번 컴퓨터부터 시작하여 웜 바이러스가 감염되는 컴퓨터의 개수를 반환하는 문제이다. 문제는 BFS/DFS 탐색을 통해 1번 노드로부터 탐색 가능한 영역을 찾는 문제이다. 초기에 입력되는 그래프의 정보를 양방향으로 기록하고 탐색을 진행하면 된다. 코드 from sys import stdin from collections import defaultdict, deque def bfs(start): q = ..

문제 16956번: 늑대와 양 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 � www.acmicpc.net 문제 풀이 크기가 RxC인 목장이 있고, 양과 늑대가 목장 안에 있다. 울타리를 설치하여 늑대가 양에 접근할 수 없으면 1을 출력하고, 아닌 경우 0을 출력한다. 늑대가 양에 접근할 수 없는 경우는 늑대와 양이 인접해있지 않은 경우이다. 문제에서 최소 울타리 개수를 구하는 것이 아닌, 늑대가 양에 접근하지 못하도록 막으면 되므로 양을 기준으로 `상, 하, 좌, 우`로 울타리를 설치하면 문제를 해결할 수 있다. 코드 from sys import stdi..