i can do ik!

BOJ 2747 피보나치 수

문제

피보나치 수는 0과 1로 시작한다. 

0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 

그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 n이 주어진다.

n은 45보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1

10

예제 출력 1

55

풀이

# boj 2747 피보나치 수

n = int(input())
fi = [0, 1]

for i in range(2, n+1):
    fi.append(fi[i-1] + fi[i-2])

print(fi[n])

BOJ 1037 약수

문제

양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 

어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 N의 진짜 약수의 개수가 주어진다.

이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다.

1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다.

출력

첫째 줄에 N을 출력한다.

N은 항상 32비트 부호있는 정수로 표현할 수 있다.

예제 입력 1

2
4 2

예제 출력 1

8

예제 입력 2

1
2

예제 출력 2

4

예제 입력 3

6
3 4 2 12 6 8

예제 출력 3

24

예제 입력 4

14
14 26456 2 28 13228 3307 7 23149 8 6614 46298 56 4 92596

예제 출력 4

185192

풀이

# boj 1037 약수

n = int(input())
a = list(map(int, input().split()))
a.sort()
print(a[0]*a[-1])

BOJ 9020 골드바흐의 추측

문제

1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 

예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 

하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 

이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 

예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다.

10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오.

만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

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

입력

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

각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.

출력

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 

출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

제한

4 ≤ n ≤ 10,000

예제 입력 1

3
8
10
16

예제 출력 1

3 5
5 5
5 11

풀이

#boj 9020 골드바흐의 추측
import sys

def is_prime(a):
    for i in range(2, int(pow(a, 0.5)) + 1):
        if a % i == 0:
            return False
    if a == 1:
        return False
    return True

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

for i in range(t):
    n = int(input())
    for a in range(n // 2, 0, -1):
        if is_prime(a) and is_prime(n - a):
            print(a, n - a)
            break

BOJ 11050 이항 계수 1

문제

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 0 ≤ K ≤ N)

출력

예제 입력 1

5 2

예제 출력 1

10

풀이

# boj 11050 이항 계수 1
import math

n, k = list(map(int, input().split()))
res = 1
for i in range(k) :
    res *= n-i

res = res // math.factorial(k)

print(res)

BOJ 25304 영수증

문제

준원이는 저번 주에 살면서 처음으로 코스트코를 가 봤다. 정말 멋졌다. 

그런데, 몇 개 담지도 않았는데 수상하게 높은 금액이 나오는 것이다! 

준원이는 영수증을 보면서 정확하게 계산된 것이 맞는지 확인해보려 한다.

영수증에 적힌,

구매한 각 물건의 가격과 개수
구매한 물건들의 총 금액

을 보고, 구매한 물건의 가격과 개수로 계산한 총 금액이 영수증에 적힌 총 금액과 일치하는지 검사해보자.

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

입력

첫째 줄에는 영수증에 적힌 총 금액 X가 주어진다.

둘째 줄에는 영수증에 적힌 구매한 물건의 종류의 수 N이 주어진다.

이후 N개의 줄에는 각 물건의 가격 a와 개수 b가 공백을 사이에 두고 주어진다.

출력

구매한 물건의 가격과 개수로 계산한 총 금액이 영수증에 적힌 총 금액과 일치하면 Yes를 출력한다. 

일치하지 않는다면 No를 출력한다.

제한

1 ≤ X ≤ 1,000,000,000
 
1 ≤ N ≤ 100
 
1 ≤ a ≤ 1,000,000
 
1 ≤ b ≤ 10

예제 입력 1

260000
4
20000 5
30000 2
10000 6
5000 8

예제 출력 1

Yes

풀이

# boj 25304 영수증

x = int(input())
n = int(input())
sum = 0

for _ in range(n):
    a, b = map(int, input().split())
    sum += a*b
if x == sum:
    print('Yes')
else:
    print('No')

BOJ 1934 최소공배수

문제

두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다.

이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 

예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다.

두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오.

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

입력

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

둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000)

출력

첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1

3
1 45000
6 10
13 17

예제 출력 1

45000
30
221

풀이

# boj 1934 최소공배수
import sys

input = sys.stdin.readline
t = int(input())
def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a

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

BOJ 16120 PPAP

문제

bryan은 PPAP를 좋아한다.

bryan은 어떻게 하면 사람들에게 PPAP를 전파할 수 있을까 고민하던 중 PPAP 문자열이라는 것을 고안하게 되었다.

PPAP 문자열은 문자열 P에서 시작하여, 문자열 내의 P를 PPAP로 바꾸는 과정을 반복하여 만들 수 있는 문자열로 정의된다. 

정확하게는 다음과 같이 정의된다.

P는 PPAP 문자열이다.
PPAP 문자열에서 P 하나를 PPAP로 바꾼 문자열은 PPAP 문자열이다.

예를 들어 PPAP는 PPAP 문자열이다. 

또한, PPAP의 두 번째 P를 PPAP로 바꾼 PPPAPAP 역시 PPAP 문자열이다.

문자열이 주어졌을 때, 이 문자열이 PPAP 문자열인지 아닌지를 알려주는 프로그램을 작성하여라.

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

입력

첫 번째 줄에 문자열이 주어진다. 

문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다.

출력

첫 번째 줄에 주어진 문자열이 PPAP 문자열이면 PPAP를, 아닌 경우 NP를 출력한다.

예제 입력 1

PPPAPAP

예제 출력 1

PPAP

예제 입력 2

PPAPAPP

예제 출력 2

NP

풀이

# boj 16120 PPAP

s = input()
stack = []
ppap = ["P", "P", "A", "P"]

for i in range(len(s)):
    stack.append(s[i])
    if stack[-4:] == ppap:
        for _ in range(4):
            stack.pop()
        stack.append("P")
if stack == ppap or stack == ["P"]:
    print("PPAP")
else:
    print("NP")

BOJ 1662 압축

문제

압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다.

K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 

이 Q라는 문자열이 K번 반복된다는 뜻이다.

압축된 문자열이 주어졌을 때, 이 문자열을 다시 압축을 푸는 프로그램을 작성하시오.

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

입력

첫째 줄에 압축된 문자열 S가 들어온다. S의 길이는 최대 50이다.

문자열은 (, ), 0-9사이의 숫자로만 들어온다.

출력

첫째 줄에 압축되지 않은 문자열의 길이를 출력한다. 이 값은 2,147,473,647 보다 작거나 같다.

예제 입력 1

33(562(71(9)))

예제 출력 1

19

예제 입력 2

123

예제 출력 2

3

예제 입력 3

10342(76)

예제 출력 3

8

예제 입력 4

0(0)

예제 출력 4

0

예제 입력 5

1(1(1(1(1(1(1(0(1234567890))))))))

예제 출력 5

0

예제 입력 6

1()66(5)

예제 출력 6

7

풀이

# boj 1662 압축

s = str(input())
tmp = ''
stack = []
l = 0
for i in s :
    if ord(i) >= 48 and ord(i) <= 57: 
        tmp, l = i, l+1
    elif i == '(' : 
        stack.append([tmp, l-1])
        l = 0
    elif i == ')' : 
        n, p = stack.pop() 
        l = int(n)*l+p 
print(l)