WEEK01 시험

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의 사이클의 길이를 구하는 프로그램을 작성하시오.

import sys
input = sys.stdin.readline

N = int(input())

new = (N % 10) * 10 + ((N // 10) + N % 10) % 10
count = 1

while N != new:
    new = (new % 10) * 10 + ((new // 10) + new % 10) % 10
    count += 1
print(count)

9095번: 1, 2, 3 더하기

정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

import sys
input = sys.stdin.readline

T = int(input())

def divide(n):
    global count
    if n < 0:
        return False
    if n == 0:
        count += 1
    if n >= 1:
        for i in range(1, 4):
            divide(n - i)
for _ in range(T):
    n = int(input())
    count = 0
    divide(n)
    print(count)

1182번: 부분수열의 합

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

재귀 사용

import sys
from itertools import combinations

input = sys.stdin.readline

N, S = map(int, input().split())
num_list = list(map(int, input().split()))

count = 0
def subset_sum(n, sum):
    global num_list, count
    if n == N:
        return
    sum += num_list[n]

    if sum == S:
        count += 1

    subset_sum(n + 1, sum)
    subset_sum(n + 1, sum - num_list[n])


subset_sum(0, 0)
print(count)

combination 사용

input = sys.stdin.readline

N, S = map(int, input().split())
num_list = list(map(int, input().split()))
count = 0

for i in range(1, N + 1):
    for nums in combinations(num_list, i):
         if sum(nums) == S:
              count += 1
print(count)