티어 : Bronze 2 시간 제한 : 2 초 메모리 제한 : 192 MB 알고리즘 분류 : 브루트포스 알고리즘
문제
어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.
자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.
입력
첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.
출력
첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.
예제 입출력
Code
N = int(input()) # 분해합
# 분해합부터 작아지면서 생성자와 생성자의 각 자리수의 합이 분해합을 만족하는지 확인
min_ = 0
for i in range(N-1, -1, -1):
temp = str(i) # i를 str형으로 변경
nums = []
# 숫자의 각 자리수를 리스트 형태로 저장
for j in range(len(temp)):
nums.append(int(temp[j]))
# 숫자의 각 자리수와 해당 숫자를 더했을 때 N이 나온다면 최솟값 갱신
if sum(nums) + i == N:
min_ = i
print(min_)
티어 : Bronze 2 시간 제한 : 2 초 메모리 제한 : 128 MB 알고리즘 분류 : 수학
문제
위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.
출력
입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.
예제 입출력
Code
N = int(input())
cum_sum = 1
count = 1
if N == 1:
print(count)
else:
while True:
cum_sum += 6 * count
count += 1
if cum_sum >= N:
print(count)
break
티어 : Silver 2 시간 제한 : 2 초 메모리 제한 : 512 MB 알고리즘 분류 : 브루트포스 알고리즘, 백트래킹
문제
오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.
BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.
N=4이고, S가 아래와 같은 경우를 살펴보자.
예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.
스타트 팀: S12+ S21= 1 + 4 = 5
링크 팀: S34+ S43= 2 + 5 = 7
1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.
스타트 팀: S13+ S31= 2 + 7 = 9
링크 팀: S24+ S42= 6 + 4 = 10
축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.
입력
첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.
출력
첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.
예제 입출력
힌트
예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.
Algorithm
back tracking - 재귀 1. start에 사람 번호 추가 2. 재귀함수 호출 3. 재귀함수가 return되면 pop 4. start의 길이가 N//2이면 능력치 구하고 차이 최솟값 갱신
Code
def back_tracking():
global answer
# start의 길이가 N//2이면 능력치 구하고 차이 최솟값 갱신
if len(start) == N//2:
s_start = 0
s_link = 0
for num1 in range(N):
for num2 in range(N):
if num1 < num2:
# 두 명 다 start 팀이면 s_start에 누적합
if num1 in start and num2 in start:
s_start += S[num1][num2] + S[num2][num1]
# 두명 다 start 팀에 없으면 s_link에 누적합
elif num1 not in start and num2 not in start:
s_link += S[num1][num2] + S[num2][num1]
# 두 팀이 능력치 차의 최솟값 갱신
if answer > max(s_start - s_link, s_link - s_start):
answer = max(s_start - s_link, s_link - s_start)
else:
for num in range(N):
# start 비어있으면 그냥 append
if not start:
start.append(num)
# start[0]이 1이 되면break
if start[0] == 1:
break
back_tracking()
start.pop()
# start 비어있지 않으면 start에 들어있지 않고 start의 마지막 값보다 큰 값만 추가
elif num not in start and num > start[-1]:
start.append(num)
# start[0]이 1이 되면break
if start[0] == 1:
break
back_tracking()
start.pop()
import sys
input = sys.stdin.readline
N = int(input())
S = []
for _ in range(N):
S.append(list(map(int, input().split())))
global answer
answer = 100*N*N
start = []
back_tracking()
print(answer)
티어 : Silver 3 시간 제한 : 2 초 메모리 제한 : 512 MB 알고리즘 분류 : 다이나믹 프로그래밍, 브루트포스 알고리즘
문제
상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.
오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.
백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.
각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.
N = 7인 경우에 다음과 같은 상담 일정표를 보자.
1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.
상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.
또한, N+1일째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.
퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이때의 이익은 10+20+15=45이다.
상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.
둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti≤ 5, 1 ≤ Pi≤ 1,000)
출력
첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.
예제 입출력
Algorithm
back tracking - 재귀 1. stack에 상담을 하는 날짜를 추가 1.1. stack이 비어있으면 오늘 날짜 추가 1.2. stack이 비어있지 않으면 T가 0이되는 날짜 추가 2. 재귀함수 호출 ☞ date를 오늘 날짜 + T로 갱신하고 인자로 전달 3. 재귀함수가 return되면 이익 더하고 pop 4. date가 마지막 값면 수익의 최댓값 갱신
Code
def back_tracking(date):
global answer
global sum_
# date가 마지막 값면 수익의 최댓값 갱신
if date == N:
if answer < sum_:
answer = sum_
date = 0
else:
while date < N:
# stack이 비어있으면
if not stack:
# 일이 끝났을 때 N을 넘지 않으면 추가
if date + info[date][0] <= N:
stack.append(date)
sum_ += info[date][1]
back_tracking(date + info[date][0])
stack.pop()
sum_ -= info[date][1]
# stack이 비어있으면 일이 끝났을 때 N을 넘지 않으면 추가
elif date + info[date][0] <= N:
stack.append(date)
sum_ += info[date][1]
back_tracking(date + info[date][0])
stack.pop()
sum_ -= info[date][1]
date += 1
back_tracking(N)
import sys
input = sys.stdin.readline
N = int(input())
info = []
for _ in range(N):
info.append(list(map(int, input().split())))
stack = []
global answer
global sum_
answer = 0
sum_ = 0
back_tracking(0)
print(answer)
티어 : Silver 1 시간 제한 : 2 초 메모리 제한 : 512 MB 알고리즘 분류 : 브루트포스 알고리즘, 백트래킹
문제
크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다. r행 c열에 있는 칸을 (r, c)라고 했을 때, (r-1, c), (r+1, c), (r, c-1), (r, c+1)에 있는 칸이 인접한 칸이다.
입력
첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에 격자판에 들어있는 수가 주어진다.
출력
선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 출력한다.
제한
1 ≤ N, M ≤ 10
1 ≤ K ≤ min(4, N×M)
격자판에 들어있는 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.
항상 K개의 칸을 선택할 수 있는 경우만 입력으로 주어진다.
예제 입출력
Algorithm
back tracking - 재귀 이용 1. graph 구현 2. 2중 for문을 돌면서 인접한 칸이 아니고 visited = False인 칸의 값을 stack에 append 3. append한 칸의 visited 값을 True로 변경하고 재귀함수 호출 4. 재귀함수 return되면 stack에서 pop하고 visited값 False로 변경 5. stack의 길이가 K가 되면 합을 구하고 합의 최댓값으로 갱신
Code
def back_tracking(x, y):
global answer
global sum_
# stack의 길이가 K가 되면 합을 구하고 합의 최댓값 갱신
if len(stack) == K:
if answer < sum_:
answer = sum_
else:
while x < N:
while y < M:
# stack이 비어있으면
if not stack:
# (x, y)의 visited값이 False면 append
if not visited[x][y]:
stack.append((x, y))
visited[x][y] = True
sum_ += int(graph[x][y])
# 이 때의 x, y값을 인자로 재귀함수 호출
back_tracking(x, y)
# 재귀함수가 return되면 pop하고 visited False로 변경
stack.pop()
visited[x][y] = False
sum_ -= int(graph[x][y])
# (x, y)의 visited = False이고 인접한 칸이 아니면 append
elif not visited[x][y] and (x-1, y) not in stack and (x+1, y) not in stack and (x, y-1) not in stack and (x, y+1) not in stack:
stack.append((x, y))
visited[x][y] = True
sum_ += int(graph[x][y])
# 이 때의 x, y값을 인자로 재귀함수 호출
back_tracking(x, y)
# 재귀함수가 return되면 pop하고 visited False로 변경
stack.pop()
visited[x][y] = False
sum_ -= int(graph[x][y])
y = y + 1
x = x + 1
y = 0
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
graph = []
for _ in range(N):
graph.append(input().rstrip().split())
global answer
global sum_
answer = -10000 * K - 1
sum_ = 0
stack = []
visited = [[False for _ in range(M)] for _ in range(N)]
back_tracking(0, 0)
print(answer)
티어 : Silver 3 시간 제한 : 1 초 메모리 제한 : 512 MB 알고리즘 분류 : 백트래킹
문제
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.
N개의 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
고른 수열은 비내림차순이어야 한다.
길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입출력
Algorithm
백트래킹 이용 1. 입력 리스트 오름차순 정렬 2. for문을 돌면서 stack 비었는지 확인하며 숫자 append 2.1. stack 비어있으면 바로 append 2.2. stack 비어있지 않으면 num이 stack 마지막 원소보다 크거나 같은 경우에만 append 3. 재귀함수 호출 4. 재귀함수 return되면 pop5. stack의 길이가 M이 되면 print
Code
def back_tracking():
# stack 길이가 M이 되면 print
if len(stack) == M:
print(' '.join(list(map(str, stack))))
else:
for num in nums:
# stack 비어있으면 num append
if not stack:
stack.append(num)
back_tracking()
stack.pop()
# 그렇지 않으면 stack 마지막 원소보다 크거나 같은 값만 append
elif stack[-1] <= num:
stack.append(num)
back_tracking()
stack.pop()
N, M = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()
stack = []
back_tracking()
티어 : Silver 3 시간 제한 : 1 초 메모리 제한 : 512 MB 알고리즘 분류 : 백트래킹
문제
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.
N개의 자연수 중에서 M개를 고른 수열
같은 수를 여러 번 골라도 된다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입출력
Algorithm
백트래킹 이용 1. 입력 리스트 오름차순 정렬 2. for문을 돌면서 숫자 append 3. 재귀함수 호출 4. 재귀함수 return되면 pop 5. stack의 길이가 M이 되면 print
Code
def back_tracking():
# stack의 길이가 M이 되면 print
if len(stack) == M:
print(' '.join(list(map(str, stack))))
else:
# stack에 num 추가
for num in nums:
stack.append(num)
back_tracking()
stack.pop()
N, M = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()
stack = []
back_tracking()
