Coding Test
네트워크 선자르기 (Bottom-Up, Top-Down)
bottom up """ 현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다. 예를 들어 4m의 네트워크 선이 주어진다면 5가지 방법을 생각할 수 있습니다 1) 1m+1m+1m+1m 2) 2m+1m+1m 3) 1m+2m+1m 4) 1m+1m+2m 5) 2m+2m 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법? 첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다. """ # Bottom-Up n=int(input()) d=[0]*(n+1) d[1]=1 d[2]=2 for i in range(3,n+1): d[i]=d[i-1]+d[i-2] print(d) print(d[n]) top down n=int(input()) d=[0]*(n+1) d[1]=1 d[2]..
[13251] 조약돌 꺼내기
13251번: 조약돌 꺼내기 첫째 줄에 뽑은 조약돌이 모두 같은 색일 확률을 출력한다. 정답과의 절대/상대 오차는 10-9까지 허용한다. www.acmicpc.net 풀이 1. 색깔별 조약돌의 개수에서 k를 뽑을 수 잇는 경우의수 / 전체 돌에 관해 k개를 뽑는 경우의 수 import sys input=sys.stdin.readline import math m = int(input()) # 색 종류개수 arr = list(map(int,input().split())) # 색깔별 조약돌 개수 k = int(sys.stdin.readline()) # 뽑을 개수 t = sum(arr) # 전체 조약돌 개수 total = math.comb(t, k) # 전체 돌에 관해 k개를 뽑는 경우의 수 same_color..
[1010] 다리 놓기
1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 분석 서쪽N ≤ 동쪽 M 다리끼리 서로 겹쳐질 수 없다 ➔ 동쪽에서 N개를 선택한 후 가장 위쪽 사이트에서부터 차례대로 연결 M개의 사이트에서 N개를 선택하는 문제로 변경 풀이 """ 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수 입력의 ..
[2775] 부녀회장이 될테야
2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net """ a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다. 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k(1 ≤ k), 두 번째 줄에 정수 n(n ≤ 14) """ import sys input=sys.stdin.readline d=[[0 for j in range(15)] for i in ra..
사다리 타기 (DFS)
""" 다리 표현은 2차원 평면은 0으 로 채워지고, 사다리는 1로 표현합니다 현수는 특정도착지점으로 도착하기 위해서는 몇 번째 열에서 출발해야 하는지 알고싶습니다. 특정 도착지점은 2로 표기됩니다 특정목적지인 2에 도착하려면 7번 열 출발지에서 출발하면 됩니다. 10*10의 사다리 지도가 주어집니다. 1 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 0 1 0 1 1 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 1 1 1 0 1 0 1 1 0 1 0 0 1 0 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 1 1 0 1 0 0 2 0 1 0 1 출발지 열 번호를 출력 """ import sys ..
[7576] 토마토 (BFS)
7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net """ 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향 에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 현수는 창고에 보관된 토마토들이 며칠이 지나 면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 첫 줄에는 상자의 크기를..
[2468] 안전영역(DFS)
2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net import sys sys.setrecursionlimit(10**6) input=sys.stdin.readline # 네 방향 탐색을 위한 상수 → ↓ ← ↑ dr=[0,1,0,-1] dc=[1,0,-1,0] n=int(input()) graph=[list(map(int, input().split())) for _ in range(n)] # print(graph) def DFS(i,j,h): visited[i][j]=True for d in range(4): next..
[2468] 안전영역(BFS)
2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 6 8 2 6 2 3 2 3 4 6 6 7 3 3 2 7 2 5 3 6 8 9 5 2 7 """ 어떤 지역의 높이 정보를 파악, 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역 최대 몇 개인지 조사 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠김 안전영역 : 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역 높이가 4 이하인 모든 지점이 물에 잠김 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠..