[Python] 다양한 문제 풀어보기

동아리 마지막 과제

여러 문제 풀어보기! 

 

https://www.acmicpc.net/workbook/view/8708

여기에 있는 다양한 유형의 문제들을 풀어본다.

---

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

import sys
input = sys.stdin.readline

# 예제 : 10 10 2 2 -> 16
# 예제 : 50000 50000 11 9 -> 20835000
H, W, N, M = map(int, input().split()) 
a = H//(N+1)
if H%(N+1)!=0:
    a+=1
b = W//(M+1)
if W%(M+1)!=0:
    b+=1

print(a*b)

• 단순 사칙연산 문제.
• 나는 if문을 이용했지만, 그냥 나누기 연산 후 반올림을 해주는게 편할 듯

 

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

import sys
input = sys.stdin.readline

S = set()
M= int(input())
for _ in range(M):
    k = list(map(str, input().split()))
    if k[0] == 'add':
        S.add(int(k[1]))
    elif k[0]=='remove':
        if int(k[1]) in S:
            S.remove(int(k[1]))
    elif k[0]=='check':
        if int(k[1]) in S:
            print(1)
        else:
            print(0)
    elif k[0]=='toggle':
        if int(k[1]) in S:
            S.remove(int(k[1]))
        else:
            S.add(int(k[1]))
    elif k[0]=='all':
        S = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
    else:
        S = set()

• 그냥 구현 문제. python에서 {}는 dictionary이므로 set()으로 집합을 선언한다.

 

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

n = int(input())
if n % 2 == 0:
    print('CY')
else:
    print('SK')

• 1이면 CY, 2이면 SK, 3이면 CY...해서 단순하게 점화식을 구할 수 있다.
• 원리는 돌을 1개 혹은 3개를 가져갈 수 있으므로 한 쪽이 이기는 경우의 수는 n-2, n-4...가 되고, 나머지는 n-1, n-3...이 되는 것. 결국 홀수/짝수로 답을 구할 수 있따.

 

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

# 내 풀이
# 반례
# 1
# 1 19 20 17 18 15 16 13 14 11 12 9 10 7 8 5 6 3 4 1 2

P = int(input())

for _ in range(P):
    T = list(map(int, input().split()))
    max_A = 0
    ans = 0
    for i in range(len(T)-1):
        if max_A<T[i+1]:
            max_A=T[i+1]
        else:
            ans += (i)
    print(T[0], ans)

• 단순 구현을 하면 되는 줄 알았는데 왜 안되지

# 정답 풀이
P=int(input())
for _ in range(P):
    arr=list(map(int,input().split()))
    total=0
    for i in range(1,len(arr)-1):
        for j in range(i+1,len(arr)): # i 뒤에 애들과 전부 비교해서
            if arr[i] > arr[j]:  # i가 더 크면
                arr[i],arr[j] = arr[j],arr[i]  # 자리바꾸기
                total+=1
    print(arr[0], total)

• 문제 이해를 잘 못 했다. 버블 정렬에서 교환 횟수를 세는 문제.

 

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

N, K = map(int, input().split())
N_list = []
for _ in range(N):
    a = list(map(int, input().split()))
    N_list.append(a)
G_list = sorted(N_list, key=lambda x : (-x[1], -x[2], -x[3]))
# print(G_list)
ans = [0]*(N+1) # 답
num = 1 # 등수

for i in range(N):
    if i==0:
        ans[G_list[i][0]] = num
    else:
        if G_list[i][1:] != G_list[i-1][1:]:
            num=(i+1)
            ans[G_list[i][0]] = num
        else:
            ans[G_list[i][0]] = num

print(ans[K])
#20점 넘기 반례
#4 3
#1 1 0 0
#2 2 0 0
#3 1 0 0
#4 2 0 0

• lambda를 이용해 금메달, 은메달, 동메달 순으로 내림차순 다중정렬을 수행한다.
• 그 후 맨 앞부터 돌며 앞 국가와 공동 순위 인지 확인하고 해당 국가의 번호를 인덱스로 ans 리스트에 등수를 저장한다.
• 처음에 20점이 나왔는데, 공동 순위가 있는 경우를 잘 고려 해야 한다. 앞 국가의 개수 +1이 자신의 순위 이므로 (i+1)이 순위가 된다. 공동일 때는 더하지 않고 그대로 순위 유지.

 

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

a = ['a','e','i','o','u']

while True:
    n = input()
    k = 0
    if n=='end':
        break
    if not('a' in n or 'e' in n or 'i' in n or 'o' in n or 'u' in n):
        k=1

    if len(n)>=3:
        for i in range(len(n)-2):
            b = [x for x in n[i:i+3] if x not in a] # a - n[i:i+3]
            if len(b)==0 or len(b)==len(n[i:i+3]):
                k=1

    if len(n)>=2:
        for i in range(len(n)-1):
            if not(n[i]=='e' or n[i]=='o'):
                if n[i]==n[i+1]:
                    k=1

    if k==1:
        print("<"+n+">"+" is not acceptable.")
    else:
        print("<"+n+">"+" is acceptable.")

• 그냥 구현 문제 2번 조건에서 리스트끼리의 뺼셈 구현이 조금 복잡했다. set()으로도 할 수 있었지만..귀찮았음.

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

import sys
input = sys.stdin.readline

N, G = map(str, input().split())
n_list = set()
for _ in range(int(N)):
    n_list.add(input())
if G=='Y':
    print(len(n_list)//1)
elif G=='F':
    print(len(n_list)//2)
else:
    print(len(n_list)//3)

• set()을 이용하여 개별 플레이어가 몇명인지 구한 후 게임에 맞게 몫을 구해준다.
• 입력 횟수가 꽤 있으므로 sys를 이용해 input을 빠르게 해주자. 시간초과는 안나지만 꽤 걸림.

 

 

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

import sys
input = sys.stdin.readline

N = int(input())
cookie = [input().strip() for _ in range(N)]
ans = [0,0,0,0,0]

head_T = False
for i in range(N): # 행
    for j in range(N): # 열
        if not head_T and cookie[i][j]=='*':
            head = [i, j]
            head_T=True

# 팔 구하기
for i in range(N):
    # 왼쪽 팔
    if cookie[head[0]+1][i]=='*' and i<head[1]:
        ans[0]+=1
    # 오른쪽 팔
    elif cookie[head[0]+1][i]=='*' and i>head[1]:
        ans[1]+=1

# 허리 구하기
for i in range(head[0]+2, N):
    if cookie[i][head[1]]=='*':
        ans[2] += 1
    else:
        leg = i # 다리를 세기 위해 기록
        break

# 다리 구하기
for i in range(leg, N):
    # 왼쪽 다리
    if cookie[i][head[1]-1]=='*':
        ans[3]+=1
    if cookie[i][head[1]+1]=='*':
        ans[4]+=1

print(head[0]+2, head[1]+1)
print(*ans)

• 구현 문제. 먼저 구하기 쉬운 머리의 좌표를 구한 후 팔/허리/다리 로 나누어 각각 구해주었다.
• 출력은 머리가 아닌 심장이므로 주의!

 

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

# 정답 풀이
N, new_score, P = map(int, input().split())
if N!=0:
    now_list = list(map(int, input().split()))
    if N==P and now_list[-1]>=new_score:
        print(-1)
    else:
        rank = N+1
        for i in range(N):
            if now_list[i]<=new_score:
                rank = i+1
                break
        print(rank)
else:
    print(1)

• https://alpyrithm.tistory.com/68

[알고리즘][Python] 백준(BOJ) 1205 등수 구하기_파이썬

• 반례를 잘 찾아서 해야 하고, N과 P의 차이를 잘 이용해야 한다.
• for문으로 주어진 점수 리스트를 돌면서 현재 score와 비교하고 rank를 부여한다. 이 때  N==P이고 가장 작은 점수가 새로운 점수보다 크다면 -1을 출력한다.
• for문을 돌았는데 새로운 점수보다 작은 점수가 없다면 N+1이 rank가 된다.

 

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

N = int(input())
N_list = list(map(int, input().split()))
M = int(input())

N_list.sort()
if sum(N_list)<M:
    print(N_list[-1])
else:
    max_num = 0
    for i in range(N):
        max_num = max(max_num, (M-sum(N_list[:i]))//(N-i))
    print(max_num)

• 단순 연산. 만약 예산액의 총 합이 M을 넘지 않는다면 최댓값을 출력한다.
• 만약 넘는다면, 예산액 리스트를 오름차순으로 돌면서 최대 상한액을 찾는다. for문을 통해 M에서 특정 예산액을 뺀 후 남은 금액을 나눠줌.

 

---

# 회고

 

한..10개씩 정리할 거임. 일단 실버까지는 문제 없이 풀면 좋겠는데 될지는 모르겠다...ㅎ

이거 하고 내가 약한 분야를 다시 복습하자.