IT-garden

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

• 1+1+1+1
• 2+1+1 (1+1+2, 1+2+1)
• 2+2
• 1+3 (3+1)

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 10,000보다 작거나 같다.

출력

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

예제 입력과 출력

정답

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

t=int(input())
dp=[[0,0,0,0] for i in range(10001)]

dp[1][1]=1

dp[2][1]=1
dp[2][2]=1

dp[3][1]=1
dp[3][2]=1
dp[3][3]=1

for i in range(4,10001):
    dp[i][1] = dp[i-1][1]
    dp[i][2] = dp[i-2][1] + dp[i-2][2]
    dp[i][3] = dp[i-3][1] + dp[i-3][2] + dp[i-3][3]

while t:
    t -= 1
    print(sum(dp[int(input())]))

dp[i][1] : 끝의 자리가 1인 경우의 수
dp[i][2] : 끝의 자리가 2인 경우의 수
dp[i][3] : 끝의 자리가 3인 경우의 수

dp[i][1]은 dp[i-1][1] 뒤에 1을 추가합니다.
dp[i][2]은 dp[i-2][1], dp[i-2][2] 뒤에 2을 추가합니다.
dp[i][3]은 dp[i-3][1], dp[i-3][2], dp[i-3][3] 뒤에 3을 추가합니다.

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

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

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

위 세문제와 관련 있는 문제입니다.

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

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력과 출력

알고리즘 분류

다이나믹 프로그래밍 

정답

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

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

dp=[[0]*201 for i in range(201)]

for i in range(201):
    dp[1][i]=1
    dp[2][i]=i+1

for i in range(2,201):
    dp[i][1]=i
    for j in range(2,201):
        dp[i][j]=(dp[i][j-1]+dp[i-1][j] )% 1000000000

print(dp[k][n])

n과 k의 관계에 대해 생각해보았습니다.

k에 상관없이 n이 1인 경우에 합이 n이 되는 경우의 수는 k개입니다.

ex) k = 2 이고 n = 1 이면 (0, 1) (1, 0) 2개

ex) k = 4 이고 n = 1 이면 (0, 0, 0, 1) (0, 0, 1, 0) (0, 1, 0, 0) (1, 0, 0, 0) 4개

k = 1 이면 n에 상관없이 합이 n이 되는 경우의 수는 1개입니다. (n 자신 1개)

k = 2 이면

위의 예제에서처럼 n = 20 이면 21개입니다.

(10,10) 1개와

(0, 20) (1, 19) (2, 18) (3, 17) (4, 16) (5, 15) (6, 14) (7, 13) (8, 12) (9, 11) 10가지를 순서 바뀐 경우로 20가지

20 + 1 = 21

n = 3 이면 (3, 0) (1, 2) 2가지를 순서 바뀐 경우로 4가지, 총 4가지입니다.

이를 통해 k = 2 이면 합이 n이 되는 경우의 수는 n+1개입니다.

k = 3 이면

n = 2 일 때 (0, 1, 1) (1, 1, 0) (1, 0, 1) (0, 0, 2) (0, 2, 0) (2, 0, 0) 6개입니다.

n = 3 일 때 (0, 0, 3) (0, 3, 0) (3, 0, 0) (0, 1, 2) (0, 2, 1) (1, 0, 2) (1, 2, 0) (2, 0, 1) (2, 1, 0) (1, 1, 1) 10개입니다.

이를 표로 표현하면 다음과 같습니다.

이를 통해 점화식 dp[i][j] = dp[i][j-1]+dp[i-1][j] (i, j가 2 이상인 경우) 를 도출할 수 있습니다. 

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

문제

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)

1. D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
2. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
3. L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
4. R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다.

여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.

1234 →L 2341 →L 3412
1234 →R 4123 →R 3412

따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.

n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.

입력

프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.

출력

A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다.

예제 입력과 출력

알고리즘 분류

BFS

정답

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

t=int(input())

def bfs(n):
    de=deque()
    de.append(n)
    ch=[-1]*10000
    ch[n]=''
    
    while de:
        x=de.popleft()

        if x == b:
            return ch[b]
    
        no,nx=divmod(2*x, 10000) #D
        if ch[nx] == -1:
            ch[nx]=ch[x]+'D'
            de.append(nx)
        
        if x == 0: #S
            nx = 9999
        else:
            nx=x-1
        
        if ch[nx] == -1:
            ch[nx]=ch[x]+'S'
            de.append(nx)
        
        nx=(x%1000)*10 + x//1000 #L
        if ch[nx] == -1:
            ch[nx]=ch[x]+'L'
            de.append(nx)
        
        nx=(x%10)*1000 + x//10 #R
        if ch[nx] == -1:
            ch[nx]=ch[x]+'R'
            de.append(nx)

while t:
    t -= 1
    a,b=map(int,input().split())
    print(bfs(a))

파이썬 시간초과로 PyPy3로 제출했습니다.

문제가 많이 어렵진 않았지만 L과 R에 해당하는 계산식을 생각하느라 시간을 많이 사용했습니다.
수학적 계산을 많이 사용해봐야겠다고 생각했습니다.

배열 ch에 이전 이동 방향을 넣고 각각 해당하는 D, S, L, R을 넣어주고 b가 되는 순간 출력했습니다.

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

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 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,-1] for i in range(100002)]

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

    while de:
        x=de.popleft()
        
        if x == k:
            return ch[k][0]

        for i in (x*2,x+1,x-1):
            if 0 <= i < 100001:
                if ch[i][0] == -1:
                    ch[i][0]=ch[x][0]+1
                    ch[i][1]=x # 이전에 방문했던 곳
                    de.append(i)

print(bfs(n)) # 가장 빠른 시간

li=deque()
li.append(k)

while True: # 어떻게 이동했는지 추적
    if ch[k][1] != -1:
        li.appendleft(ch[k][1])
        k=ch[k][1]
    else:
        break

print(' '.join(map(str,li)))

ch배열을 2차로 잡습니다.
ch[i][0]은 해당 지점에 가는데 걸린 시간이고 ch[i][1]은 이전에 방문했던 지점을 표시합니다.

ch[i][1]을 통해 끝에서부터 추적해서 어떻게 이동했는지 출력합니다.

백준알고리즘 - 1697번 숨바꼭질 - 파이썬(Python)

백준알고리즘 - 13549번 숨바꼭질 3 - 파이썬(Python)

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

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

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

예제 입력과 출력

정답

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

n=int(input())
w=[list(map(int,input().split())) for i in range(n)]
a=[i for i in range(n)]

r=10000000

def _10971(li):
    s=0
    
    for j in range(n-1):
        if w[li[j]][li[j+1]] != 0:
            s += w[li[j]][li[j+1]]
        else:
            return -1

    if w[li[-1]][li[0]] == 0:
        return -1
    else:
        s += w[li[-1]][li[0]]
    return s

for li in permutations(a):
    print(li)
    c= _10971(li)
    if c != -1:
        r=min(r,c)

print(r)

파이썬 시간초과로 PyPy3로 제출했습니다.

순열을 이용해 모든 가능한 경우를 확인합니다.
각 도시를 이동하는 비용을 더하는데 비용이 0인 경우는 이동할 수 없으니까 불가능한 경우라고 생각합니다.
또한 마지막 도시에서 여행을 출발했던 도시로 돌아올 때도 비용이 0이면 불가능한 경우라고 생각합니다.
가능한 경우 중 가장 적은 비용을 출력합니다.

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

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

예제 입력과 출력

정답

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

n=int(input())
a=list(map(int,input().split()))

p=list(permutations(a,n))
r=0

for i in p:
    s=0
    li=list(i)
    for j in range(1,n):
        s += abs(li[j]-li[j-1])
    r=max(r,s)

print(r)

배열 a의 모든 경우의 수를 생각합니다.
순열을 이용해 각각 배열의 경우에 대한 합을 구하고 최댓값을 출력합니다.

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