문제는 #1110, #9095, #1182이다. 3문제 중 1문제 맞추는게 목표였지만, 예상과 달리 3문제를 모두 맞췄다. 물론 문제들을 효율적으로 잘 풀어내진 못했다고 생각한다.
시험이 끝나고 바로 2주차 과제가 주어졌으나, 오늘 푼 문제를 리뷰하면서 시간을 보내려고 한다. 차례대로 푼 문제를 리뷰해보자.!!
1. 더하기 사이클(#1110)
문제
0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, 주어진 수의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수를 이어 붙이면 새로운 수를 만들 수 있다. 다음 예를 보자.
26부터 시작한다. 2+6 = 8이다. 새로운 수는 68이다. 6+8 = 14이다. 새로운 수는 84이다. 8+4 = 12이다. 새로운 수는 42이다. 4+2 = 6이다. 새로운 수는 26이다.
위의 예는 4번만에 원래 수로 돌아올 수 있다. 따라서 26의 사이클의 길이는 4이다.
N이 주어졌을 때, N의 사이클의 길이를 구하는 프로그램을 작성하시오.입력
첫째 줄에 N이 주어진다. N은 0보다 크거나 같고, 99보다 작거나 같은 정수이다.
출력
첫째 줄에 N의 사이클 길이를 출력한다.
이 문제는 입력받은 숫자를 문자로 바꾸고 문자열 연결을 해주는 걸 반복해주면 된다. 단, 10보다 작으면 앞에 0을 붙여 두 자리 수로 만들어주면된다.
from sys import stdin
input = stdin.readline
n = int(input())
cnt = 0
if n < 10:
s = '0' + str(n)
else:
s = str(n)
while True:
temp = int(s[0]) + int(s[1])
temp = str(temp)
s = s[1] + temp[len(temp)-1]
cnt += 1
if int(s) == n: break
print(cnt)2. 1, 2, 3 더하기(#9095)
문제
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
- 1+1+1+1
- 1+1+2
- 1+2+1
- 2+1+1
- 2+2
- 1+3
- 3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.
출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
문제를 보고 재귀로 돌리면 되겠다고 생각했다. 생각한 방식은 백트래킹 방식으로 경우의 수를 구해서 하면 되겠다고 생각하고 문제를 풀어보았다. 1, 2, 3으로 만들 수 있는 경우의 수를 만들면서 중간에 그 합이 입력한 값하고 같으면 체크를 해준다. 또한 불필요한 탐색을 줄이기 위해 중간에 합이 입력한 값보다 커지면 바로 return해주는 방식으로 구현했다.
- 원본코드
from sys import stdin
input = stdin.readline
n = int(input())
temp = []
cnt = 0
def dsf(T, depth):
global cnt
if sum(temp) == T:
cnt += 1
return
if sum(temp) > T: return
if depth == 0: return
for i in range(1, 4):
temp.append(i)
dsf(T, depth-1)
temp.pop()
for _ in range(n):
T = int(input())
dsf(T, T)
print(cnt)
cnt = 0코드 리뷰을 하면서 if depth == 0: return 이 부분이 왜 있어야 되는 건지에 대한 질문을 받았다. 처음에는 당연히 길이가 끝까지가면 있어야된다고 생각했는데 질문을 받고 생각한 결과 depth == 0일 경우는 모든 배열이 1로만 이루어진 경우 밖에 없는데 그 부분은 if sum(temp) == T 조건문에서 리턴이 된다는 사실을 알게 되었다.
- 수정코드
from sys import stdin
input = stdin.readline
n = int(input())
temp = []
cnt = 0
def dsf(T, depth):
global cnt
if sum(temp) == T:
cnt += 1
return
if sum(temp) > T: return
for i in range(1, 4):
temp.append(i)
dsf(T, depth-1)
temp.pop()
for _ in range(n):
T = int(input())
dsf(T, T)
print(cnt)
cnt = 03. 부분수열의 합(#1182)
문제
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
출력
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.```
이 문제 또한 위 1, 2, 3 더하기 문제와 같이 백 트래킹 방식으로 풀어 보았다. 중복되지 않는 경우의 수를 찾아서 그들의 합이 입력한 값하고 같으면 return을 하는 방식으로 풀었다.
from sys import stdin
input = stdin.readline
n, s = map(int, input().split())
arr = list(map(int, input().split()))
temp = []
cnt = 0
def dsf(depth, idx):
global cnt
global s
global n
if sum(temp) == s and depth != 0:
cnt += 1
if depth == n:
return
for i in range(n):
if idx < i:
temp.append(arr[i])
dsf(depth + 1, i)
print(temp)
temp.pop()
dsf(0, -1)
print(cnt)마지막으로 오늘 다른 사람들이 작성한 코드를 보면서 다양한 방법으로 풀 수 있었다는 것을 배웠고, 1, 2, 3 더하기 문제에서 불필요한 조건문 하나를 지울 수 있는 코드 리뷰도 들었다. 앞으로 코드를 작성할 때 생각한 것보다 조금 더 고민해야겠다고 생각한다.
