i can do ik!

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

시간 제한 : 1 초
메모리 제한 : 512 MB

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 

각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

출력

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

예제 입력 1

3
4
7
10

예제 출력 1

7
44
274

풀이

t = int(input()) 
dp = [0]*(1001) 
dp[0] = 1

for i in range(t):   
    n = int(input())    
    for i in range(1,n+1):   
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    print(dp[n])

BOJ 1463 1로 만들기

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

    X가 3으로 나누어 떨어지면, 3으로 나눈다.
    X가 2로 나누어 떨어지면, 2로 나눈다.
    1을 뺀다.
    
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 

연산을 사용하는 횟수의 최솟값을 출력하시오.

시간 제한 : Python 3: 1.5 초
메모리 제한 : 128 MB

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1

2

예제 출력 1

1

예제 입력 2

10

예제 출력 2

3

풀이

n = int(input())
dp = [0 for i in range(n+2)]
dp[1] = 0
dp[2] = 1

for i in range(3,n+1):
    dp[i] = dp[i-1] + 1
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)
        
print(dp[n])

BOJ 9237 이장님 초대

문제

농부 상근이는 마당에 심기 위한 나무 묘목 n개를 구입했다. 

묘목 하나를 심는데 걸리는 시간은 1일이고, 상근이는 각 묘목이 다 자라는데 며칠이 걸리는지 정확하게 알고 있다.

상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 

이장님을 실망시키면 안되기 때문에, 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 

즉, 마지막 나무가 다 자란 다음날 이장님을 초대할 것이다.

상근이는 나무를 심는 순서를 신중하게 골라 이장님을 최대한 빨리 초대하려고 한다. 

이장님을 며칠에 초대할 수 있을까?

시간 제한 : 1 초
메모리 제한 : 128 MB

입력

입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 

둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000)

출력

첫째 줄에 며칠에 이장님을 초대할 수 있는지 출력한다.

답이 여러 가지인 경우에는 가장 작은 값을 출력한다. 묘목을 구입한 날이 1일이다.

예제 입력 1

4
2 3 4 3

예제 출력 1

7

예제 입력 2

6
39 38 9 35 39 20

예제 출력 2

42

풀이

n = int(input())
t = list(map(int,input().split()))
t.sort(reverse=True)
res = 0

for i in range(n):
    res = max(res, t[i]+i)

print(res+2)

BOJ 1715 카드 정렬하기

문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 

각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 

이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 

이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 

예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 

합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 

그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 

(10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 

최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

시간 제한 : 2 초 
메모리 제한 : 128 MB

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 

숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 비교 횟수를 출력한다.

예제 입력 1

3
10
20
40

예제 출력 1

100

풀이

import heapq
import sys

input = sys.stdin.readline
n = int(input())
card = []

for _ in range(n):
    num = int(input())
    heapq.heappush(card, num)

res = 0

while len(card)>1:
    n1 = heapq.heappop(card)
    n2 = heapq.heappop(card)
    res += n1 + n2
    heapq.heappush(card, n1+n2)

print(res)

BOJ 10819 차이를 최대로

문제

N개의 정수로 이루어진 배열 A가 주어진다. 

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

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

시간 제한 : 1 초 
메모리 제한 : 256 MB

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 

둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 

배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

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

예제 입력 1

6
20 1 15 8 4 10

예제 출력 1

62

풀이

from itertools import permutations

n = int(input())
numbers = list(map(int, input().split()))
res = []

for per in permutations(numbers, n):
    tmp = 0
    for i in range(n - 1):
        tmp += abs(per[i] - per[i + 1])
    res.append(tmp)

print(max(res))

BOJ 1057 토너먼트

문제

김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 

토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 

그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 

이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 

만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 

다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 

이때, 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 

이 말은 1번과 2번이 스타를 해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 

4번은 다음 라운드에서 번호 2번을 배정받는다. 

번호를 다시 배정받은 후에 한 명만 남을 때까지 라운드를 계속 한다.

마침 이 스타 대회에 임한수도 참가했다. 

김지민은 갑자기 스타 대회에서 우승하는 욕심은 없어지고, 몇 라운드에서 임한수와 대결하는지 궁금해졌다. 

일단 김지민과 임한수는 서로 대결하기 전까지 항상 이긴다고 가정한다. 

1 라운드에서 김지민의 번호와 임한수의 번호가 주어질 때, 

과연 김지민과 임한수가 몇 라운드에서 대결하는지 출력하는 프로그램을 작성하시오.

시간 제한 : 1 초
메모리 제한 : 512 MB

입력

첫째 줄에 참가자의 수 N과 1 라운드에서 김지민의 번호와 임한수의 번호가 순서대로 주어진다. 

N은 2보다 크거나 같고, 100,000보다 작거나 같은 자연수이고, 

김지민의 번호와 임한수의 번호는 N보다 작거나 같은 자연수이고, 서로 다르다.

출력

첫째 줄에 김지민과 임한수가 대결하는 라운드 번호를 출력한다. 

만약 서로 대결하지 않을 때는 -1을 출력한다.

예제 입력 1

16 1 2

예제 출력 1

1

예제 입력 2

16 8 9

예제 출력 2

4

예제 입력 3

1000 20 31

예제 출력 3

4

예제 입력 4

65536 1000 35000

예제 출력 4

16

풀이

n, jm, hs = map(int, input().split())

round = 0

while (n > 1) and (jm != hs) :
    n -= n//2
    jm -= jm//2
    hs -= hs//2
    round += 1

if n == 1 and jm != hs :
    round -= 1

print(round)

처음에 n을 사용 안하고 풀었으나 주어진 입력값을 전부 사용하기 위해 수정

다른 방법을 좀더 찾아봐야겠다

BOJ 2702 초6 수학

문제

두 정수 a와 b 최소공배수는 두 수의 공통된 배수 중 가장 작은 수이고, 

최대공약수는 두 수의 공통된 약수중 가장 큰 수이다.

a와 b가 주어졌을 때, 최소공배수와 최대공약수를 구하는 프로그램을 작성하시오.

시간 제한 : 1 초
메모리 제한 : 128 MB

입력

첫째 줄에 테스트 케이스의 개수 T(1<=T<=1,000)가 주어진다. 

각 테스트 케이스는 두 정수 a와 b로 이루어져 있고, 공백으로 구분되어 있다. (1 <= a,b <= 1,000)

출력

각 테스트 케이스에 대해 최소공배수와 최대공약수를 차례대로 출력한다.

예제 입력 1

3
5 10
7 23
42 56

예제 출력 1

10 5
161 1
168 14

풀이

import sys

def lcm(a, b) :
  return int((a*b) / gcd(a, b))

def gcd(a, b) :
  if a == 0 :
    return b
  else :
    return gcd(b % a, a)

input = sys.stdin.readline
t = int(input())

for i in range(t) :
    a, b = map(int, input().split())
    print(lcm(a, b), gcd(a, b))

BOJ 1120 문자열

문제

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 

예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.

두 문자열 A와 B가 주어진다. 

이때, A의 길이는 B의 길이보다 작거나 같다. 

이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

    A의 앞에 아무 알파벳이나 추가한다.
    A의 뒤에 아무 알파벳이나 추가한다.

이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

시간 제한 : 2 초 
메모리 제한 : 128 MB

입력

첫째 줄에 A와 B가 주어진다. 

A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력

A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

예제 입력 1

adaabc aababbc

예제 출력 1

2

예제 입력 2

hello xello

예제 출력 2

1

예제 입력 3

koder topcoder

예제 출력 3

1

예제 입력 4

abc topabcoder

예제 출력 4

0

예제 입력 5

giorgi igroig

예제 출력 5

6

풀이

import sys

input = sys.stdin.readline
a, b = input().split()
res = list()

for i in range(len(b) - len(a)+1):
    cnt = 0
    for j in range(len(a)):
        if(a[j] != b[j+i]):
            cnt += 1
    res.append(cnt)
    
print(min(res))