옛날에 풀었던 문제이지만, 동적 프로그래밍을 복습하는 과정에서 가장 기초적인 문제라 다시 한 번 풀어보았다.
문제를 풀고 나서 옛날에 풀었던 것을 확인 해보았는 데...
N = int(input())
for i in range(int(N/5)+1,0,-1):
if (N-5*i)%3==0 and N-5*i>=0:
print(int(i+(N-5*i)/3))
exit()
if(N%3==0):
print(int(N/3))
exit()
else:
print(-1)
어떻게 풀었는 지는 모르겠지만, 동적프로그래밍이 아니라 그냥 계산으로 푼 것 같다...
동적 프로그래밍답게 지난 계산을 기억할 배열을 만들고 해당 데이터가 존재한다면 그 데이터를 이용해서 현재 데이터를 만들 수 있게 했다.
import sys
N = int(sys.stdin.readline())
sugar = [-1 for i in range(N + 3)]
sugar[3] = 1
sugar[4] = -1
sugar[5] = 1
for i in range(6, N+1):
if sugar[i-3] == -1 and sugar[i-5] == -1:
sugar[i] = -1
elif sugar[i-3] == -1:
sugar[i] = sugar[i-5] + 1
elif sugar[i-5] == -1:
sugar[i] = sugar[i-3] + 1
else:
sugar[i] = min(sugar[i-3], sugar[i-5]) + 1
print(sugar[N])
3, 4, 5에 대한 값을 미리 넣어줘야 하는 데 배열을 N+1로 만들어버리면 index 에러가 발생해서
그냥 N+3만큼 미리 만들어버리고 시작했다.
그리고 후에는 반복문을 돌며 3번 전, 5번 전의 계산에서 유효한 값이 있다면 그 중 작은 값에서 +1을 한다
만약 둘 중 하나만 유효한 값이라면 그 값의 +1을 하고, 둘 다 유효하지 않다면 만들 수 없는 경우이기 때문에 -1로 만들어준다.
우선 입력받은 배열을 바로 정렬하고, 그 배열로 부분집합을 만드는 것까지는 바로 생각이 난다.
하지만 그렇게 만든 부분집합에서 조건으로 걸러야 한다.
make_key(cur_candidate + [candidate[index]], index + 1)
make_key(cur_candidate, index + 1)
이렇게 재귀함수로 현재의 값을 추가하는 집합 하나, 추가하지 않는 집합 하나를 만들어준다.
def make_key(cur_candidate, index):
if index == C:
value = len(set(cur_candidate).intersection(important))
if len(cur_candidate) == L and value >= 1 and (L - value) >= 2:
for i in cur_candidate:
print(i, end='')
print()
return
else:
make_key(cur_candidate + [candidate[index]], index + 1)
make_key(cur_candidate, index + 1)
이렇게 하나씩 추가하다가 인덱스가 C를 넘어갔을 때, 현재 부분집합의 길이가 L이고 모음이 하나 이상 있고 자음이 2개 이상 있을 때만 출력이 되도록 해줬다.
import sys
L, C = map(int, sys.stdin.readline().split())
candidate = sorted(list(map(str, sys.stdin.readline().split())))
important = {'a', 'e', 'i', 'o', 'u'}
def make_key(cur_candidate, index):
if index == C:
value = len(set(cur_candidate).intersection(important))
if len(cur_candidate) == L and value >= 1 and (L - value) >= 2:
for i in cur_candidate:
print(i, end='')
print()
return
else:
make_key(cur_candidate + [candidate[index]], index + 1)
make_key(cur_candidate, index + 1)
make_key([], 0)
하지만 2, 4, 6, 8... 이렇게는 셀프 넘버가 아닌 것을 보고 d(1) = 1 + 1 = 2가 된다는 것을 깨닫고 풀 수 있게 되었다.
만약 푸는 중간에 알게 되었다면 고생 좀 했을 것 같다.
우선 d(n)에 대한 함수를 만들어주자.
def d(n):
d_result = n
while n > 9:
d_result += (n % 10)
n //= 10
return d_result + n
해당 수와 쪼갠 수들을 모두 더해서 반환해주는 d(n) 함수이다.
result = [True for i in range(1, 10001)]
def d(n):
d_result = n
while n > 9:
d_result += (n % 10)
n //= 10
return d_result + n
for i in range(1, 10000):
if result[i]:
print(i)
num = i
while num < 10000:
num = d(num)
if num < 10000:
result[num] = False
1부터 10000까지 반복을 하면서 만약 result[i]에 대한 수가 True라면 해당 수를 출력하고, 그 수로 만들 수 있는 수들을 연쇄적으로 모두 지워준다.
def hansoo(num):
hansoo_list = []
while num > 0:
hansoo_list.append(num % 10)
num //= 10
for t in range(len(hansoo_list) - 2):
if hansoo_list[t+1] - hansoo_list[t] != hansoo_list[t+2] - hansoo_list[t+1]:
return False
return True
우선 해당 수가 한수인지 판별해주는 함수이다.
만약 100 미만의 수가 들어오면 배열의 크기가 2 이하가 되기 때문에 무조건 True가 반환되게 된다.
100 이상의 수가 들어오게 된다면, 해당 수를 모두 쪼개서 배열에 저장한다.
그리고 반복문을 통해 간격이 다른 구간이 있다면 바로 False를 반환한다.
import sys
N = int(sys.stdin.readline())
result = 0
def hansoo(num):
hansoo_list = []
while num > 0:
hansoo_list.append(num % 10)
num //= 10
for t in range(len(hansoo_list) - 2):
if hansoo_list[t+1] - hansoo_list[t] != hansoo_list[t+2] - hansoo_list[t+1]:
return False
return True
for i in range(1, N + 1):
if hansoo(i):
result += 1
print(result)
요즘 브루투 포스 알고리즘을 풀면서 생각하는 건데 브루트 포스 문제는 백트래킹 기법을 같이 사용해서 푸는 문제가 많은 것 같다.
재귀함수를 이용하다보니 조건을 만족하면 되돌아 오는 백트래킹을 많이 쓰는 것 같다.
덕분에 함수 다루는 실력이 좀 향상된것 같다. ㅎㅎ (지극히 내 생각이다.....)
함수를 2개 사용했다.
첫 번째 함수는 현재 있는 멤버에 새로운 친구가 들어갈 수 있는지 확인해주는 함수이다.
# 새로 들어온 친구가 들어갈 수 있는지 확인하는 함수이다.
# 리스트에 첫 번째 인덱스는 0이 있으니 제외하고 시작하자.
def is_friend(plus_friend, member_list):
for q in member_list[1:]:
if plus_friend not in friends[q]:
return False
return True
굳이 설명할 필요가 없을 거라고 생각된다.
두번째 함수는 재귀함수 + 백트래킹 함수 + 탐색 함수이다.
이 함수가 핵심이다.
# cur_cnt는 현재 만들어진 멤버의 수, cur_list는 그 멤버의 번호이다.
def find_friends(cur_cnt, cur_list):
# 멤버를 K명 모으면 함수를 종료한다. (재귀함수의 기저사례)
if cur_cnt == K:
for q in cur_list[1:]:
print(q)
return True
# 순서대로 들어가기 때문에 cur_list에 있는 번호가 가장 큰 멤버는 -1의 인덱스에 있다.
# 대신 빈 리스트에 -1을 부르면 에러가 뜨기 때문에 이 함수 호출 전에 반복문으로 0을 넣어주고 시작한다.
for q in range(cur_list[-1] + 1, N + 1):
if is_friend(q, cur_list):
cur_list.append(q)
if find_friends(cur_cnt + 1, cur_list):
return True
cur_list.pop()
return False
우선 함수가 종료되는 조건은 멤버의 수가 K가 되는 조건이다.
글을 작성하면서 생각해보니 굳이 cur_cnt를 쓰지 않고 len함수를 이용해서 인수를 하나 줄일 수 있었을 것 같다.
아래 반복문은 아직 확인하지 않은 값을 is_friend로 확인하면서 가능하다면 해당 멤버를 추가해 다시 함수를 호출하는 부분이다.
백트래킹에서 사용하듯이 만약 해당 값으로 답을 찾을 수 없다면 다 확인해본 후에 pop등을 이용해서 값을 빼주어야 한다.
import sys
K, N, F = map(int, sys.stdin.readline().split())
friends = [[] for i in range(N + 1)]
for i in range(F):
a, b = map(int, sys.stdin.readline().split())
friends[a].append(b)
friends[b].append(a)
# 새로 들어온 친구가 들어갈 수 있는지 확인하는 함수이다.
# 리스트에 첫 번째 인덱스는 0이 있으니 제외하고 시작하자.
def is_friend(plus_friend, member_list):
for q in member_list[1:]:
if plus_friend not in friends[q]:
return False
return True
# cur_cnt는 현재 만들어진 멤버의 수, cur_list는 그 멤버의 번호이다.
def find_friends(cur_cnt, cur_list):
# 멤버를 K명 모으면 함수를 종료한다. (재귀함수의 기저사례)
if cur_cnt == K:
for q in cur_list[1:]:
print(q)
return True
# 순서대로 들어가기 때문에 cur_list에 있는 번호가 가장 큰 멤버는 -1의 인덱스에 있다.
# 대신 빈 리스트에 -1을 부르면 에러가 뜨기 때문에 이 함수 호출 전에 반복문으로 0을 넣어주고 시작한다.
for q in range(cur_list[-1] + 1, N + 1):
if is_friend(q, cur_list):
cur_list.append(q)
if find_friends(cur_cnt + 1, cur_list):
return True
cur_list.pop()
return False
if not find_friends(0, [0]):
print(-1)
이 문제의 전체코드이다.
import sys
K, N, F = map(int, sys.stdin.readline().split())
friend = {i+1: [] for i in range(N)}
for i in range(F):
first, second = map(int, sys.stdin.readline().split())
friend[first].append(second)
friend[second].append(first)
def judge(plus_friend, members):
for per in members:
if per not in friend[plus_friend]:
return False
return True
def backtracking(per_cnt, cur_members):
if per_cnt == K:
for i in cur_members:
print(i)
exit(0)
for i in range(cur_members[-1] + 1, N + 1):
if judge(i, cur_members):
backtracking(per_cnt + 1, cur_members + [i])
for i in range(1, N):
backtracking(1, [i])
print(-1)
전에 풀었던 코드인데 재귀함수를 빠져나올 방법을 찾지 못해서 그냥 exit로 프로그램을 종료해버렸었다.
물론 이렇게 풀어도 되기는 하지만 재귀함수, 백트래킹을 제대로 사용하기 위해 함수를 빠져 나올 수 있는 방법을 생각하며 풀어야겠다.