Jinho Tech

단순한 백트래킹 문제이다.

def dfs(depth):
    if depth == 6:
        print(*li)
        return ;
    for i in range(n):
        if check[i]:
            continue
        li.append(nums[i])
        check[i] = 1
        dfs(depth+1)
        li.pop()
        for j in range(i+1, n):
            check[j] = 0
        
while 1:
    t = list(map(int, input().split()))
    n, nums = t[0], t[1:]
    if n == 0:
        break
    li = []
    check = [0]*n
    dfs(0)
    print()

수학 & 백트래킹 문제이다. 그런데 백트래킹을 써서 푸니까 시간 초과가 나온다.

시간 초과가 뜰 만 한 코드이긴 한데 어떻게 해결해야 할지 모르겠어서 일단 반복문을 사용해서 해결했다.

반복문 풀이(통과)

N = int(input())
s = set()
for i in range(N+1):
    for j in range(N+1 - i):
        for k in range(N+1 - i - j):
            t = N-i-j-k
            n = i + 5*j + 10*k  + 50*t
            s.add(n)

print(len(s))

백트래킹 풀이(시간 초과)

def dfs(depth, s):
    if depth == N:
        check[s] = 1
        return ;
    for i in range(4):
        dfs(depth+1, s+nums[i])
        
N = int(input())
nums = [1, 5, 10, 50]
check = [0]*(50*20+1)
dfs(0, 0)
cnt = 0
for i in check:
    if i:
        cnt += 1
print(cnt)

기본적인 다이나믹 프로그래밍 문제이다.

R, C, W = map(int, input().split())
li = [[1], [1, 1]]
for i in range(2, R+W-1):
    t = [1]
    for j in range(1, i):
        t.append(li[i-1][j-1]+li[i-1][j])
    t.append(1)
    li.append(t)
res, w = 0, 1
for i in range(R-1, R+W-1):
    for j in range(w):
        res += li[i][C-1+j]
    w += 1
print(res)

기본적인 다이나믹 프로그래밍 문제이다.

n, k = map(int, input().split())
li = [[1], [1, 1]]
for i in range(2, n):
    t = [1]
    for j in range(1, i):
        t.append(li[i-1][j-1]+li[i-1][j])
    t.append(1)
    li.append(t)
print(li[n-1][k-1])

단순 수학 문제이다.

n = int(input())
cnt = 0
for i in range(3, max(n-6, 0)+1, 3):
    for j in range(i+3, max(n-3, 0)+1, 3):
        cnt += 1
print(cnt)

단순 수학 문제이다. 조금 꼼수를 써서 풀었다.

s = input()
c_li = s.split('d')
d_li = s.split('c')
res = 1
for c in c_li:
    if c == '': continue
    res = res * 26 * 25**(len(c)-1)
for d in d_li:
    if d == '': continue
    res = res * 10 * 9**(len(d)-1)
print(res)

조합 문제이다.

단순히 조합을 계산하고 뒤에 0의 개수를 새면 시간 초과가 걸리기 때문에 효율적인 방법을 찾아야 된다.

아래의 코드가 처음에는 이해가 잘 안될수도 있다. 예시를 들어 풀다 보면 이해가 더 잘 될 것이다.

n, m = map(int, input().split())

def cnt2(n):
    n2 = 0
    while(n != 0):
        n //= 2
        n2 += n
    return n2

def cnt5(n):
    n5 = 0
    while(n != 0):
        n //= 5
        n5 += n
    return n5

print(min(cnt2(n)-cnt2(m)-cnt2(n-m), cnt5(n)-cnt5(m)-cnt5(n-m)))