2025.03.20
TIL(TODAY I LEARN)
오늘은 첫주차 시험을 치뤘다. 시간내에 1182 - 부분수열의 합 문제를 풀지 못했다. 시험이 끝나고 다시 풀어봤더니 메모리 초과가 뜨더라. 다시 풀어냈다. 뿌듯하다.
1110 - 더하기 사이클
문제 설명
N의 사이클 길이를 구하는 문제입니다. 주어진 수에 대해 다음과 같은 규칙으로 새로운 수를 만들어 냅니다:
입력 조건
- 0 ≤ N ≤ 99 (정수)
규칙
- 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만듭니다.
- 각 자리의 숫자를 더합니다.
- 원래 수의 오른쪽 자리와 합의 오른쪽 자리를 이어 붙여 새로운 수를 만듭니다.
예시
N = 26인 경우:
- 2 + 6 = 8 → 새로운 수: 68
- 6 + 8 = 14 → 새로운 수: 84
- 8 + 4 = 12 → 새로운 수: 42
- 4 + 2 = 6 → 새로운 수: 26
26은 4번 만에 원래 수로 돌아옵니다. 따라서 사이클의 길이는 4입니다.
내 코드
import sys
input = sys.stdin.readline
N = int(input().strip())
cnt = 0
new_N = 0
def sol(N,start):
global new_N
global cnt
if start == new_N:
return
cnt +=1
x = N % 10 + N // 10
new_N = (N % 10) * 10 + x%10
sol(new_N,start)
x = N * 10 if N < 10 else N
sol(x,x)
if x == 0:
print(1)
else:
print(cnt)9095 - 1,2,3 더하기
문제 설명
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제입니다.
입력 조건
- 1 ≤ n ≤ 11 (정수)
규칙
- 정수 n을 1, 2, 3의 합으로 나타내야 합니다.
- 같은 수를 여러 번 사용할 수 있습니다.
- 순서가 다른 경우는 다른 방법으로 간주합니다.
예시
n = 4인 경우:
- 1+1+1+1
- 1+1+2
- 1+2+1
- 2+1+1
- 2+2
- 1+3
- 3+1
총 7가지 방법이 있습니다.
내 코드
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
num = [1,2,3]
T = int(input().strip())
def sol(n,sumN):
global cnt
if sumN > n:
return
if sumN == n:
cnt +=1
return
for i in num:
sumN += i
sol(n,sumN)
sumN -= i
for _ in range(T):
cnt = 0
n = int(input().strip())
sol(n,0)
print(cnt)
새로운 방식의 코드(DP)
import sys
input = sys.stdin.readline
def solution(n):
if n == 1:
return 1
elif n == 2:
return 2
elif n == 3:
return 4
else:
return solution(n-1) + solution(n-2) + solution(n-3)
T = int(input().strip())
for _ in range(T):
n = int(input().strip())
print(solution(n))1182 - 부분수열의 합
문제 설명
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 문제입니다.
입력 조건
- 1 ≤ N ≤ 20
- |S| ≤ 1,000,000
- 주어지는 정수의 절댓값은 100,000을 넘지 않음
규칙
- 수열의 원소를 선택하거나 선택하지 않는 모든 경우를 고려해야 합니다.
- 최소 하나의 원소는 선택해야 합니다.
- 선택된 원소들의 합이 S가 되어야 합니다.
예시
N = 5, S = 0인 경우:
수열: -7 -3 -2 5 8
- -3 -2 5 = 0
- -2 2 = 0
총 2가지 방법이 있습니다.
내 코드
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N,S = map(int,input().split())
n_list = list(map(int,input().split()))
sum_list = []
sol_list = set()
#visited = [False] * N
def sol(s,idx):
global cnt
if s == sum(sum_list) and len(sum_list) > 0:
#sol_list.add(tuple((sorted(sum_list[:]))))
cnt += 1
for i in range(idx, len(n_list)):
#if visited[i] == False:
sum_list.append(n_list[i])
# visited[i] = True
sol(s,i+1)
# visited[i] = False
sum_list.pop()
cnt = 0
sol(S,0) # 순열뽑기 조합으로 어떻게? 이차원배열에서 중복제거?
# idx 현재 인덱스를 추가해서 다음 배열에서 배열 시작지점을 골라줌
print(cnt)
#print(sol_list)
#print(len(sol_list))
^_^