공작소

문제 링크 : https://www.acmicpc.net/problem/7576풀이 과정익은 토마토 1을 시작으로, 너비 우선 탐색을 이용했다. 인접한 모든 토마토가 익는 날짜를 계산하면 된다.토마토의 전체 개수를 파악하여, 익지 않은 토마토가 존재하는지 여부 또한 파악해야 한다. 전체 코드# 7576 : 토마토import sysfrom collections import dequeinput = sys.stdin.readlinem, n = map(int, input().rstrip().split())arr = [list(map(int, input().rstrip().split())) for _ in range(n)]visited = [[False for _ in range(m)] for _ in range..

문제 링크 : https://www.acmicpc.net/problem/18870풀이 과정1. 좌표 값 순으로 정렬한 후 인덱스를 부여한다. (동일 값은 동일 인덱스)2. 기존 인덱스 순으로 정렬한 후 압축된 좌표의 인덱스를 출력한다. 전체 코드# 18870 : 좌표 압축import sysfrom collections import dequeinput = sys.stdin.readlinen = int(input().rstrip())arr = list(map(int, input().rstrip().split()))narr = [[arr[i], i, 0] for i in range(n)] # [좌표 값, 인덱스, 압축된 좌표 인덱스]# 좌표 압축narr.sort(key=lambda x:(x[0], x[1]))..

문제 링크 : https://www.acmicpc.net/problem/11727풀이 과정타일로 채우는 상황을 떠올려보자. 현재 $ 2 \times k $ 까지 채운 상태라고 해보자. (= $k$ 번 열까지)$ 2 \times (k+1) $ 까지 채우기 위해선 1×2 (세로 직사각형) 타일 1개를 채우는 방법 1개가 있다.$ 2 \times (k+2) $ 까지 채우기 위해선 1×2 (세로 직사각형) 타일 2개, 2×1 (가로 직사각형) 타일 2개, 2×2 (정사각형) 타일 1개를 채우는 방법 3개가 있다. 이를 반대로 생각해보자. $ 2 \times k $ 까지 채우기 위해선1. $ 2 \times (k-1) $ 까지 채운 상태에서 1×2 (세로 직사각형) 타일 1개를 채우는 방법 1개 (O)2. $ ..

문제 링크 : https://www.acmicpc.net/problem/2606풀이 과정주어진 컴퓨터들과의 간선 관계를 그래프로 보고, 1번 컴퓨터부터 시작하는 너비 우선 탐색을 진행한다.이렇게 탐색함으로써, 네트워크 상으로 1번 컴퓨터와 연결된 컴퓨터들의 개수를 셀 수 있다. 유의해야 할 점쌍방향 간선으로 등록해야 한다. 어느 쪽 방향으로든 탐색 가능하기 때문이다. ( u -> v / v -> u )탐색 도중 방문 처리가 되어야 중복 탐색을 피할 수 있다. (visited)탐색하면서 컴퓨터들의 개수를 셀 때, 1번 컴퓨터도 맨 처음 탐색에 들어가기 때문에 result 값을 초기에 -1 으로 설정하여 1번 컴퓨터를 제외시켰다.전체 코드# 2606 : 바이러스import sysfrom collections..

문제 링크 : https://www.acmicpc.net/problem/11047풀이 과정필요한 동전 개수가 최소여야 한다.주어진 동전을 액수 기준으로 내림차순한 뒤, 가장 액수가 큰 동전부터 사용한다. 가장 액수가 적은 동전이 1원이니 액수 K는 반드시 맞출 수 있다.전체 코드# 11047 : 동전 0import sysinput = sys.stdin.readline# Input n, k = map(int, input().rstrip().split())arr = [int(input().rstrip()) for _ in range(n)]# 내림차순 정렬 후 K 제거하면서 동전 개수 확보arr.sort(reverse=True)result = 0for i in range(n): result += (k /..

문제 링크 : https://www.acmicpc.net/problem/9461 풀이 과정그림으로부터 점화식을 유추하여 DP 테이블을 정의한다.$ dp[i] = dp[i-3] + dp[i-2] $ 전체 코드# 9461 : 파도반 수열import sysinput = sys.stdin.readline# Calculate P(N)dp = [0 for _ in range(101)]dp[1] = 1dp[2] = 1for i in range(3, 101): dp[i] = dp[i-3] + dp[i-2]# Input & Outputt = int(input().rstrip())for _ in range(t): print(dp[int(input().rstrip())])