IT-garden

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍
냅색

정답

import sys
input= lambda : sys.stdin.readline().strip()

n=int(input())
dp=[0]*(n+1)

a=[i**2 for i in range(1, 317)]

for i in range(1,n+1):
    s=[]
    
    for j in a:
        if i < j:
            break
        s.append(dp[i-j])
        
    dp[i] = min(s) + 1

print(dp[n])

i보다 j가 작거나 같은 제곱수들이라고 생각하면 점화식은 dp[i]=min(dp[i-j])+1 입니다.

백준 알고리즘 1699번 : https://www.acmicpc.net/problem/1699

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} 이고, 길이는 3이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍 

정답

import sys
input= lambda : sys.stdin.readline().strip()

n=int(input())
a=list(map(int,input().split()))
dp=[1]*n

for i in range(n-1,-1,-1):
    for j in range(n-1,i-1,-1):
        if a[i] > a[j]:
            dp[i]=max(dp[i],dp[j]+1)
            
print(max(dp))

수열 A = {10, 20, 10, 30, 20, 50} 이라면
부분 수열은 {10}, {10, 20}, {10, 20, 30}, {10, 20, 30, 20} 과 같은 것이 있습니다.
이 중 부분수열이 전부 감소하는 요소로 된 것을 감소하는 부분 수열이라 합니다.
가장 긴 감소하는 부분 수열은 부분수열 중 모두 감소하는 요소로 된 길이가 긴 부분수열입니다.

백준 11053번에서의 범위를 반대로 해주면 되는 문제입니다.

[알고리즘/백준알고리즘] - 백준알고리즘 - 11053번 가장 긴 증가하는 부분 수열 - 파이썬(Python)

백준 알고리즘 : https://www.acmicpc.net/problem/11722

문제

정수 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은 양수이며 1,000,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

예제 입력과 출력

정답

import sys
input= lambda : sys.stdin.readline().strip()

t=int(input())
m=[0]*1000001
m[1]=1
m[2]=2
m[3]=4

while t:
    t -= 1
    a=int(input())
    if a <= 3:
        print(m[a])
    else:
        if m[a] != 0:
            print(m[a])
            continue
        for i in range(4,a+1):
            if m[i] != 0:
                continue
            else:
                m[i]= (m[i-1]+m[i-2]+m[i-3]) % 1000000009
        print(m[a])

백준알고리즘 - 9095번 1, 2, 3 더하기 - 파이썬(Python)

위 문제의 응용 문제입니다.

백준 알고리즘 15988번 : https://www.acmicpc.net/problem/15988

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력과 출력

정답

from collections import deque
import sys
input = lambda :sys.stdin.readline().strip()

n,k=map(int,input().split())
ch=[-1]*100001

def bfs():
    de=deque()
    de.append(n)
    ch[n] = 0

    while de:
        x=de.popleft()

        if x == k:
            return ch[k]

        if 0 <= x*2 < 100001 and ch[x*2] == -1:
            ch[x*2] = ch[x]
            de.append(x*2)
        
        for i in (x-1,x+1):
            if 0 <= i < 100001 and ch[i] == -1:
                ch[i] = ch[x]+1
                de.append(i)

print(bfs())

1697 숨바꼭질 문제에서 조금 변형된 문제입니다.

백준 알고리즘 13549번 : https://www.acmicpc.net/problem/13549

문제

영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.

영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.

영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.

출력

첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.

예제 입력과 출력

정답

from collections import deque
import sys
input = lambda :sys.stdin.readline().strip()

s=int(input())
ch=[[-1]*(s+1) for i in range(s+1)]

def bfs():
    de=deque()
    de.append([1,0])
    ch[1][0]=0

    while de:
        x,y=de.popleft()

        if ch[x][x] == -1: # 1번 연산
            ch[x][x] = ch[x][y]+1
            de.append([x,x])
        if x+y <= s and ch[x+y][y] == -1 : # 2번 연산
            ch[x+y][y] = ch[x][y]+1
            de.append([x+y,y])
        if x-1 >=0 and ch[x-1][y] == -1: # 3번 연산
            ch[x-1][y] = ch[x][y]+1
            de.append([x-1,y])
            
bfs()

r=ch[s][1]
for i in range(1,s):
    if ch[s][i] != -1:
        r=min(r,ch[s][i])
print(r)

이모티콘 1개에서 s개까지의 이모티콘을 화면에 만드는데 걸리는 최소 시간을 구하는 문제입니다.
bfs를 이용해 문제를 푸는데 ch를 이차원 배열로 만듭니다.

ch[화면에 나온 이모티콘 개수][클립보드의 이모티콘 개수]

bfs에서 1, 2, 3번 각각 연산의 경우를 실행합니다.
화면에 나온 이모티콘은 s개이고 클립보드의 이모티콘이 1부터 s-1개일때까지의 값을 비교해 가장 작은 값(최소 시간)을 출력합니다.

백준 알고리즘 14226번 : https://www.acmicpc.net/problem/14226

문제

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

예제 입력과 출력

정답

import sys
input = lambda : sys.stdin.readline().strip()

n,m=map(int,input().split())
li=[[]*m for i in range(n)]

for i in range(m):
    a,b=map(int,input().split())
    li[a].append(b)
    li[b].append(a)

def dfs(node,d):
    print(ch)
    global r
    ch[node]=0

    if d >= 4:
        r = 1
        return

    for i in li[node]:
        if ch[i] == -1:
            dfs(i,d+1)
            ch[i]= -1

r=0
ch=[-1]*n
for i in range(n):
    dfs(i,0)
    ch[i]=-1
    if r == 1:
        break

print(r)

친구관계가 존재하는지 안하는지는 5명의 친구가 순서대로 친구관계를 이루는지를 통해 확인할 수 있습니다.

dfs를 이용해 한 친구를 기준으로 길이가 4까지 갈 수 있는지 확인했습니다.

백준 알고리즘 13023번 : www.acmicpc.net/problem/13023