매일 문제 풀기 - 8월 다섯째 주

깃허브에 코딩 문제 풀기용 레포지토리를 만들었다. 깃허브에 올리는 연습을 하기 위해... 후후 깃헙과 친해질거다!!

 

 

---

 

8/28. 직각삼각형 (백준 4153번)

 

https://www.acmicpc.net/problem/4153

 

#python

import sys

while True :
    a, b, c = map(int, sys.stdin.readline().split())

    if a + b + c == 0 :
        exit()

    max = c

    if a > max :
        max = a
    if b > max :
        max = b

    if a*a + b*b + c*c == max*max*2 :
        print("right")
    else :
        print("wrong")

 

(정답)

 

---

 

8/28. 블랙잭 (백준 2798번)

 

https://www.acmicpc.net/problem/2798

 

#python

import sys

n, m = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))

max = 0

for i in range(0, n-2) :
    for j in range(i+1, n-1) :
        for k in range(j+1, n) :
            sum = data[i] + data[j] + data[k]
            if sum <= m :
                if sum > max :
                    max = sum

print(max)

 

처음엔 어려운 알고리즘을 활용해야 하는 문제인 줄 알고 고민을 좀 했는데 n이 100 이하인 것을 보니 뭔가 브루트포스일 것만 같은 느낌이 들어서 보니까 맞았다. (정답)

 

---

 

8/30. 덱 (백준 10866번)

 

https://www.acmicpc.net/problem/10866

 

#python

from collections import deque
import sys

deq = deque()
n = int(sys.stdin.readline())
count = 0

for i in range(0, n) :
    commend = sys.stdin.readline().split()

    if commend[0] == "push_front" :
        deq.appendleft(commend[1])
    elif commend[0] == "push_back" :
        deq.append(commend[1])
    elif commend[0] == "pop_front" :
        if len(deq) == 0 :
            print(-1)
        else :
            print(deq.popleft())
    elif commend[0] == "pop_back" :
        if len(deq) == 0 :
            print(-1)
        else :
            print(deq.pop())
    elif commend[0] == "size" :
        print(len(deq))
    elif commend[0] == "empty" :
        if len(deq) == 0 :
            print(1)
        else :
            print(0)
    elif commend[0] == "front" :
        if len(deq) == 0 :
            print(-1)
        else :
            print(deq[0])
    elif commend[0] == "back" :
        if len(deq) == 0 :
            print(-1)
        else : 
            print(deq[-1])
    
    count += 1

 

파이썬에 있는 collections라는 모듈 내의 deque라는 클래스를 활용했다. 나머지는 다 간단하게 해결 가능했는데, deque에는 덱의 사이즈를 구하는 메서드와 덱이 비어있는지 확인할 수 있는 메서드가 없어서 좀 고민을 했다. 그런데 찾아보니 deque은 마치 list처럼 활용할 수도 있다고 해서 사이즈는 list처럼 len(deq)으로 구했고, 덱이 비어있는지 확인하는 것도 len(que) == 0인지 확인하는 것으로 대체했다. (정답)

 

---

 

8/30. 요세푸스 문제 0 (백준 11866번)

 

https://www.acmicpc.net/problem/11866

 

#python

import sys
from collections import deque

n, k = map(int, sys.stdin.readline().split())
deq = deque()

for i in range(1, n+1) :
    deq.append(i)

print("<", end = "")

while len(deq) != 0 :
    deq.rotate(-k+1)

    if len(deq) > 1 :
        print(str(deq.popleft()) + ", ", end = "")
    else :
        print(str(deq.popleft()) + ">")

 

클래스 deque에 있는 메서드 rotate를 활용했다. deque.rotate(n)은 n만큼의 원소의 위치를 회전시킨다. (양수: 시계방향, 음수: 반시계방향) n에 -(k-1)이라는 값을 넣으면 k번째 원소가 맨 앞에 나오게 된다. 아 참고로 나는 값과 ", "라는 문자열을 같이 출력하기 위해 +를 사용했는데, deq.popleft()는 숫자이기 때문에 str로 변환해주어야 한다. len(deq)가 0이 되기 전까지 반복문을 돌렸고, len(deq) > 1 이면 값 뒤에 ", "를 출력하고, len(deq) == 1 이면 값 뒤에 ">"를 출력하도록 했다. (정답)

 

---

 

8/31. 이항 계수 1 (백준 11050번)

 

https://www.acmicpc.net/problem/11050

 

#python

import sys

n, k = map(int, sys.stdin.readline().split())

ans = 1

for i in range(k+1, n+1) :
    ans *= i

for i in range(1, n-k+1) :
    ans /= i

print(int(ans))

 

nCk = n! / ( k! * (n-k)! ) = ( n*(n-1)*...*(k+1) ) / (n-k)! 이걸 그대로 코드로 구현했다. 물론 팩토리얼 함수를 만들어서 푸는 방법도 있겠지만 이게 더 효율적인 것 같아서 이렇게 했다. 나누기를 했으므로 마지막에 ans를 int로 바꿔주고 출력하는 거 잊지 말기! (정답)