1. 특정 거리의 도시 찾기
문제 유형 : BFS
문제 링크 : https://www.acmicpc.net/problem/18352
18352번: 특정 거리의 도시 찾기
첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개
www.acmicpc.net
🐥 문제 설명
어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.
이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.
예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.
이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.
입력
첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.
출력
X로부터 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 K인 모든 도시의 번호를 한 줄에 하나씩 오름차순으로 출력한다.
이 때 도달할 수 있는 도시 중에서, 최단 거리가 K인 도시가 하나도 존재하지 않으면 -1을 출력한다.
🐥 문제 풀이
1. 모든 간선의 비용이 동일할 때에는 너비 우선 탐색인 BFS를 이용하여 최단 거리를 구할 수 있다.
2. 방문한 노드들을 표시해두고 방문한 노드와 연결되어 있는 노드들 중 방문하지 않은 노드를 큐에 넣어준다.
3. 큐가 빌 때 까지 진행~!
🐥 문제 풀이 코드
import sys
from collections import deque
f = sys.stdin.readline
# 도시개수, 도로 개수, 거리 정보, 출발 도시 정보
n, m , k , x = map(int, f().split())
graph = [[] for _ in range(n+1)]
distance= [0] * (n+1)
visited = [False] * (n+1)
for i in range(m):
start, end = map(int, f().split())
graph[start].append(end)
def bfs(x):
answer = []
q = deque([x])
visited[x] = True
distance[x] =0
while q :
city = q.popleft()
for next_city in graph[city]:
if visited[next_city] != True:
q.append(next_city)
visited[next_city] = True # 다음 번에 방문하더라도 이번 방문이 최단 거리가 되기 때문에 visited True를 설정을 통해 다음 부터 연산 안되게!
distance[next_city] = distance[city]+1
if distance[next_city]==k: # 해당 최단 경로가 k이면
answer.append(next_city)
if len(answer) == 0 :
print(-1)
else:
for x in sorted(answer):
print(x)
return 0
bfs(x) # bfs 시작 x 노드 부터2. 연구소
문제 유형 : BFS / DFS
문제 링크 : https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크
www.acmicpc.net
🌱 문제 설명
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.
연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.
이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.
2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.
바이러스가 퍼진 뒤의 모습은 아래와 같아진다.
벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
빈 칸의 개수는 3개 이상이다.
출력
첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.
🌱 문제 풀이
1. 이 문제는 DFS, BFS 두 방법으로 모두 풀 수 있다.
2. 벽을 설치할 수 있는 경우의 수를 모두 구한 뒤 벽이 3개가 설치 되었을 때의 안전 영역 크기를 구한다.
3. DFS 를 통해 울타리 설치 영역을 선택하고 3개의 울타리 설치가 되었을 때 dfs 또는 bfs로 바이러스를 퍼뜨리고 안전 영역을 구한다.
🌱 문제풀이 코드
from collections import deque
import copy
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
ans =0
dx = [ 0, 0, 1, -1] # 오, 왼, 위, 아
dy = [1, -1, 0, 0]
def calc_safe():
graph_v = copy.deepcopy(graph)
q = deque([])
for i in range(n): # 바이러스 정보 담기
for j in range(m):
if graph_v[i][j]==2:
q.append((i,j))
while q: # bfs 시작
v_x, v_y = q.popleft()
for i in range(4):
n_x,n_y = v_x+dx[i], v_y +dy[i]
if 0<=n_x<n and 0<=n_y<m :
if graph_v[n_x][n_y]==0:
graph_v[n_x][n_y]=2 # 감염
q.append((n_x, n_y))
global ans
safe_count =0
for i in range(n): # 안전지대 계산
safe_count+=graph_v[i].count(0)
ans = max(ans, safe_count)
def choose_wall(w_count):
if w_count==3:
calc_safe()
return
for i in range(n):
for j in range(m):
if graph[i][j]==0 : # 울타리를 세울 수 있는 곳이면
graph[i][j]=1
choose_wall(w_count+1)
graph[i][j] =0 # 백트래킹
choose_wall(0)
print(ans)
# 코드 2 / Dfs 기반
n, m = map(int, input().split())
data = [] # 초기 맵 리스트
temp = [[0]*m for _ in range(n)]
for _ in range(n):
data.append(list(map(int, input().split())))
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
result =0
def virus(x,y): # dfs를 사용하여 바이러스가 사방으로 퍼지게 함.
for i in range(4):
nx = x +dx[i]
ny = y+dy[i]
if nx >=0 and nx< n and ny >=0 and ny<m :
if temp[nx][ny]==0:
temp[nx][ny]=2
virus(nx, ny)
def get_score():
score = 0
for i in range(n):
for j in range(m):
if temp[i][j]==0:
score+=1
return score
def dfs(count):
global result
if count ==3 :
for i in range(n):
for j in range(m):
temp[i][j] = data[i][j]
for i in range(n): # 바이러스 전파
for j in range(m):
if temp[i][j] ==2:
virus(i,j)
result = max(result, get_score())
return
for i in range(n):
for j in range(m):
if data[i][j]==0:
data[i][j] =1
count+=1
dfs(count)
data[i][j]=0 #백트래킹
count -=1
dfs(0)
print(result)3. 경쟁적 전염
문제 유형 : BFS
문제 링크 : https://www.acmicpc.net/problem/18405
18405번: 경쟁적 전염
첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치
www.acmicpc.net
💡 문제 설명
NxN 크기의 시험관이 있다. 시험관은 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 바이러스가 존재할 수 있다. 모든 바이러스는 1번부터 K번까지의 바이러스 종류 중 하나에 속한다.
시험관에 존재하는 모든 바이러스는 1초마다 상, 하, 좌, 우의 방향으로 증식해 나간다. 단, 매 초마다 번호가 낮은 종류의 바이러스부터 먼저 증식한다. 또한 증식 과정에서 특정한 칸에 이미 어떠한 바이러스가 존재한다면, 그 곳에는 다른 바이러스가 들어갈 수 없다.
시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오. 만약 S초가 지난 후에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다. 이 때 X와 Y는 각각 행과 열의 위치를 의미하며, 시험관의 가장 왼쪽 위에 해당하는 곳은 (1,1)에 해당한다.
예를 들어 다음과 같이 3x3 크기의 시험관이 있다고 하자. 서로 다른 1번, 2번, 3번 바이러스가 각각 (1,1), (1,3), (3,1)에 위치해 있다. 이 때 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류를 계산해보자.
1초가 지난 후에 시험관의 상태는 다음과 같다.
2초가 지난 후에 시험관의 상태는 다음과 같다.
결과적으로 2초가 지난 뒤에 (3,2)에 존재하는 바이러스의 종류는 3번 바이러스다. 따라서 3을 출력하면 정답이다.
입력
첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치에 존재하는 바이러스의 번호가 공백을 기준으로 구분되어 주어진다. 단, 해당 위치에 바이러스가 존재하지 않는 경우 0이 주어진다. 또한 모든 바이러스의 번호는 K이하의 자연수로만 주어진다. N+2번째 줄에는 S, X, Y가 공백을 기준으로 구분되어 주어진다. (0 ≤ S ≤ 10,000, 1 ≤ X, Y ≤ N)
출력
S초 뒤에 (X,Y)에 존재하는 바이러스의 종류를 출력한다. 만약 S초 뒤에 해당 위치에 바이러스가 존재하지 않는다면, 0을 출력한다.
💡 문제 풀이
1. 이 문제는 BFS 로 풀 수 있다.
2. 먼저 초기 바이러스 정보를 큐에 넣어둔다. ( 바이러스 번호 순서대로 sort 해서 )
3. 큐가 빌때까지 큐의 길이만큼 반복문을 돌면서 방문하지 않은 노드들에 대해 전염을 시킨다.
4. 큐의 길이만큼 도는 것이 끝나면 1초가 끝난 것이다. 초 수를 증가하고 초 수가 s와 동일할 때 종료!
💡 문제 풀이 코드
import sys
from collections import deque
f = sys.stdin.readline
def bfs(s, x, y):
count = 0
q = deque(virus)
while q :
if count == s:
break
else:
for i in range(len(q)):
v_x, v_y, v_k = q.popleft()
for i in range(len(dir)): # 사방으로 전염
n_x , n_y = v_x +dir[i][0], v_y + dir[i][1]
if 0<=n_x<n and 0<=n_y<n : # 전염 시킴
if graph[n_x][n_y] == 0 :
graph[n_x][n_y]= v_k
q.append((n_x, n_y, v_k))
count+=1 # 1초 증가
return graph[x-1][y-1] # s초 후의 x,y 상태
dir = [(-1, 0), ( 1, 0), (0,-1), (0, 1)]
n, k = map(int, f().split()) # n 행 수, k 바이러스 종류
graph = [list(map(int, f().split())) for _ in range(n)]
virus =[]
for i in range(n):
for j in range(n):
if graph[i][j]!=0 :
virus.append((i, j, graph[i][j])) # 위치 , 종류 함께 저장
virus.sort(key= lambda x : x[2]) # 바이러스 번호가 작은 것 부텉 정렬
s,x,y = map(int,f().split()) # s 초 뒤에 x,y 좌표 확인
visited= [[] * n for _ in range(n)]
ans = bfs(s,x,y)
print(ans)4. 괄호 변환
문제 유형 : 재귀 ( DFS 와 비슷 )
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/60058
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
🕹 문제 설명
카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다.
수정해야 할 소스 파일이 너무 많아서 고민하던 "콘"은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.
용어의 정의
'(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다.
그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다.
예를 들어, "(()))("와 같은 문자열은 "균형잡힌 괄호 문자열" 이지만 "올바른 괄호 문자열"은 아닙니다.
반면에 "(())()"와 같은 문자열은 "균형잡힌 괄호 문자열" 이면서 동시에 "올바른 괄호 문자열" 입니다.
'(' 와 ')' 로만 이루어진 문자열 w가 "균형잡힌 괄호 문자열" 이라면 다음과 같은 과정을 통해 "올바른 괄호 문자열"로 변환할 수 있습니다.
1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
4-3. ')'를 다시 붙입니다.
4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
4-5. 생성된 문자열을 반환합니다.
"균형잡힌 괄호 문자열" p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 "올바른 괄호 문자열"로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요.
매개변수 설명
- p는 '(' 와 ')' 로만 이루어진 문자열이며 길이는 2 이상 1,000 이하인 짝수입니다.
- 문자열 p를 이루는 '(' 와 ')' 의 개수는 항상 같습니다.
- 만약 p가 이미 "올바른 괄호 문자열"이라면 그대로 return 하면 됩니다.
입출력 예
| p | result |
| "(()())()" | "(()())()" |
| ")(" | "()" |
| "()))((()" | "()(())()" |
입출력 예 #1
이미 "올바른 괄호 문자열" 입니다.
입출력 예 #2
- 두 문자열 u, v로 분리합니다.
- u = ")("
- v = ""
- u가 "올바른 괄호 문자열"이 아니므로 다음과 같이 새로운 문자열을 만듭니다.
- v에 대해 1단계부터 재귀적으로 수행하면 빈 문자열이 반환됩니다.
- u의 앞뒤 문자를 제거하고, 나머지 문자의 괄호 방향을 뒤집으면 ""이 됩니다.
- 따라서 생성되는 문자열은 "(" + "" + ")" + ""이며, 최종적으로 "()"로 변환됩니다.
입출력 예 #3
- 두 문자열 u, v로 분리합니다.
- u = "()"
- v = "))((()"
- 문자열 u가 "올바른 괄호 문자열"이므로 그대로 두고, v에 대해 재귀적으로 수행합니다.
- 다시 두 문자열 u, v로 분리합니다.
- u = "))(("
- v = "()"
- u가 "올바른 괄호 문자열"이 아니므로 다음과 같이 새로운 문자열을 만듭니다.
- v에 대해 1단계부터 재귀적으로 수행하면 "()"이 반환됩니다.
- u의 앞뒤 문자를 제거하고, 나머지 문자의 괄호 방향을 뒤집으면 "()"이 됩니다.
- 따라서 생성되는 문자열은 "(" + "()" + ")" + "()"이며, 최종적으로 "(())()"를 반환합니다.
- 처음에 그대로 둔 문자열에 반환된 문자열을 이어 붙이면 "()" + "(())()" = "()(())()"가 됩니다.
🕹 문제 풀이
1. 이 문제는 재귀함수를 이용해 풀 수 있다.
2. 문제 설명 박스에 있는 1~4의 과정을 그대로 풀이하면 된다.
🕹 문제 풀이 코드
b_str= input()
def dfs(p):
count = 0
r = True # 올바른 문자열인지 확인하는
if len(p)==0: # 빈 문자열인 경우
return p
for i in range(len(p)):
if p[i] == '(':
count-=1
else:
count+=1
if count > 0 : # '(' 보다 ')' 수가 많다는 뜻 또는 '(' 보다 ')'가 먼저 나온 경우
r = False # 올바른 문자열이 아님
if count==0 : # 균형잡힌 문자열이면
if r : # 균형잡히고 올바른 경우
return p[:i+1] + dfs(p[i+1:]) # 재귀
else: # 균형은 잡혔으나 올바르지 못한 경우
return '(' + dfs(p[i+1:])+')' + ''.join(list(map(lambda x: '(' if x ==')' else ')', p[1:i])))
print(dfs(b_str))
5. 연산자 끼워넣기
문제 유형 : DFS
문제 링크 : https://www.acmicpc.net/problem/14888
14888번: 연산자 끼워넣기
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수,
www.acmicpc.net
🐳 문제 설명
N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.
우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.
예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.
- 1+2+3-4×5÷6
- 1÷2+3+4-5×6
- 1+2÷3×4-5+6
- 1÷2×3-4+5+6
식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.
- 1+2+3-4×5÷6 = 1
- 1÷2+3+4-5×6 = 12
- 1+2÷3×4-5+6 = 5
- 1÷2×3-4+5+6 = 7
N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.
출력
첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.
🐳 문제 풀이
1. 백트래킹과 dfs를 사용하여 문제를 풀 수 있다.
2. 각 수와 수 사이에 사칙연산 중 하나를 삽입하는 모든 경우에 대하여 만들 수 있는 최솟값과 최댓값을 구한다.
3. 모든 경우의 수 계산을 위해 dfs 혹은 bfs 를 통해 해결 가능
🐳 문제 풀이 코드
max_num = -1e9
min_num= 1e9
def dfs( total, count ):
global operators,max_num, min_num
if count == n: # 식 완료
max_num = max(max_num, total)
min_num = min(min_num, total)
else:
if operators[0] > 0: # 더하기가 남았다면..
operators[0]-=1
dfs(total+numbers[count],count+1) # count 값이 1부터 시작
operators[0]+=1
if operators[1] > 0 : # 빼기가 남았다면
operators[1]-=1
dfs(total-numbers[count], count+1)
operators[1]+=1
if operators[2]>0: # 곱셈
operators[2]-=1
dfs(total*numbers[count], count+1)
operators[2]+=1
if operators[3]>0: # 나눗셈
operators[3]-=1
if total < 0 :
dfs(-((total * -1)//numbers[count]), count+1)
else:
dfs(total//numbers[count] , count+1)
operators[3]+=1
n = int(input())
numbers = list(map(int, input().split()))
operators = list(map(int, input().split())) # 덧셈, 뺼셈, 곱셈, 나눗셈 순
dfs(numbers[0],1 )
print(max_num)
print(min_num)'스터디IT🌼 > Algorithm' 카테고리의 다른 글
| [ 다이나믹 프로그래밍 = 동적계획법 ] 알고리즘 내용 정리 (0) | 2023.01.12 |
|---|---|
| [ 완전탐색 ] 알고리즘 내용 정리 (0) | 2023.01.12 |
| 알아두면 좋은 파이썬 문법 _ for 코딩테스트 (1) | 2022.10.13 |
| [ BaekJoon ] 마법사 상어와 토네이도 _ 시뮬레이션 (0) | 2022.10.11 |
| [ 프로그래머스 ] 네트워크 _ DFS (0) | 2022.10.09 |
댓글