코딩 테스트/백준 강의 연습편
BFS) 6087.레이저 통신
https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net # solution. # BFS의 가중치를 직선의 개수로 설정한다. # 즉, 시작점부터 해당점까지 도달하기 위해 필요한 직선의 개수를 dist 배열에 업데이트한다. # 여기서 필요한 직선의 개수 -1 이 필요한 거울 개수의 최솟값이므로 dist 배열의 타겟 지점의 값에서 -1을 해주면 답을 구할 수 있다. # 가중치가 다르므로, BFS 탐색을 할 때, 각 방향에서 벽을 만나거나 탐색 범위..
시뮬레이션과 구현) 16974.레벨 햄버거
https://www.acmicpc.net/problem/16974 16974번: 레벨 햄버거 상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다. 레벨-0 버거는 패티만으로 이루어져 있다. 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, www.acmicpc.net # solution. # d[i] : 레벨 i 인 햄버거의 길이. d[i]=1+d[i-1]+1+d[i-1]+1=2d[i-1]+3 # p[i] : 레벨 i 인 햄버거의 패티 개수. p[i-1]+1+p[i-1]=2p[i-1]+1 # go(n,x) : 레벨 n 버거에서 아래 x장 중 패티의 개수 반환 # if n>=1: # x==1: 0 # 1
브루트포스) 16198.에너지 모으기
https://www.acmicpc.net/problem/16198 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있 www.acmicpc.net n=int(input()) w=list(map(int,input().split())) # solution 1. 재귀 def recur(w): n = len(w) if n == 2: return 0 ans = 0 for i in range(1, n - 1): energy = w[i - 1] * w[i + 1] b = w[:i] + w[i + 1:] energy += recur(b) if ans..
브루트포스) 16197.두 동전
https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net dx = [0,0,1,-1] dy = [1,-1,0,0] # 두 동전 중 하나만 보드에서 떨어뜨리기 위해 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램 def recur(step,x1,y1,x2,y2): # 버튼을 10번보다 많이 눌러야 한다면, -1 출력 if step==11: return -1 fall1=False fall2=False # 동전이 이동하려는 방향에 칸이 없으면 동전은 보드 ..
브루트포스) 14500.테트로미노
https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net # 시간 복잡도 # 도형은 19가지 모양이 나올 수 있고, N * M 격자의 각 칸에 도형의 시작점이 놓일 수 있으므로, # O(19 * (N*M)^2) < 1억 # 솔루션 # 뫼 산 모양 하나를 제외한 나머지 모양은, 임의의 칸에서 시작하여, 연속하는 3개의 인접 칸을 방문한 것으로 나타낼 수 있다. # 따라서 뫼 산 모양 하나를 제외한 나머지는 재귀 함수로 나타낼 수 있다. dx = [0,0,..
브루트포스) 15659.연산자 끼워넣기(3)
https://www.acmicpc.net/problem/15659 15659번: 연산자 끼워넣기 (3) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net n=int(input()) nums=list(map(int,input().split())) ops = list(map(int,input().split())) max_ans=-1000000001 min_ans=10000000001 def dfs(index:int,exp:str): global max_ans,min_ans # 종료 조건 i..