[백준/정렬 - Python] 2750, 2751, 17390, 2399, 8989, 3273

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

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

2751번: 수 정렬하기 2

2750번, 2751번

import sys
input = sys.stdin.readline

n = int(input())
array = []
for _ in range(n):
    array.append(int(input()))

array.sort()

for i in range(n):
    print(array[i])

17390번

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

17390번: 이건 꼭 풀어야 해!

처음에 이런식으로 풀다가 시간초과가 났다!

import sys
input = sys.stdin.readline

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

# 매 입력마다 소수를 새로 구하면 시간초과 발생
for _ in range(q):
    l, r = map(int, input().split())
    print(sum(a[l - 1: r]))

구글링을 해보니, DP로 풀어야지 시간초과가 나지 않는다고 해서 dp로 다시 풀었다!

import sys
input = sys.stdin.readline

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

dp = [0] * (n + 1)
for i in range(1, n + 1):
    dp[i] = dp[i - 1] + a[i - 1]

for _ in range(q):
    l, r = map(int, input().split())
    print(dp[r] - dp[l - 1])

2399번

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

2399번: 거리의 합

얘도 그냥 풀었다가, 구글링해서 dp로 다시 풀었다. 

점화식 세우는게 처음에는 딱 안떠올라서 구글링 했슴다.. 

import sys
input = sys.stdin.readline

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

x.sort()
dp = [0] * (n + 1)
sum = 0
for i in range(1, n):
    dp[i] = dp[i - 1] + (x[i] - x[i - 1]) * i
    sum += dp[i]
print(sum * 2)

3273번

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

3273번: 두 수의 합

시간 초과나서 다시 .. 

import sys
input = sys.stdin.readline

n = int(input())
array = list(map(int, input().strip().split()))
x = int(input())

array.sort()
count = 0
left, right = 0 , n-1
while left < right:
    temp = array[left] + array[right]
    if temp == x:
        count+=1
        left +=1
    elif temp < x:
        left += 1
    else:
        right -= 1
print(count)

8989번

시침의 각도:  (30 * 시 + 0.5 * 분), 분침의 각도는 (6 * 분) - 구글링 ㅎㅎ

import sys
input = sys.stdin.readline

n = int(input())

for i in range(n):
    time = list(input().split())
    rank = {}
    for t in time:
        h, m = map(int, t.split(":"))
        h_deg = ((h % 12) * 30 + m / 2) % 360
        m_deg = 6 * m     
        deg = abs(h_deg - m_deg)    
        rank[t] = min(deg, 360 - deg)
        rank.append([min(deg, 360 - deg), t])
    rank.sort()
    print(rank[2][1])