Jinho Tech

k개의 로프를 사용할 때 들어 올릴 수 있는 중량은

버틸 수 있는 중량이 제일 작은 로프의 최대 중량 * k라는 점이 핵심이다. 

EX) 15, 10 로프 2개를 사용할 경우

최대 10 * 2 = 20인데 이유는 15가 10보다 큰 중량을 버틸 수 있더라도 로프에 걸리는 중량은 똑같기 때문에 10을 기준으로 최대 중량이 정해지기 때문이다.

N = int(input())
li = sorted([int(input()) for _ in range(N)], reverse=True)
ans = 0
for i in range(N):
    ans = max(ans, li[i]*(i+1))
print(ans)

단순한 수학 문제이다. 

N*M 크기의 초콜릿이 있다고 하자.

처음에 행(N) 기준으로 자르면 (N-1)번 자르게 되고 (1*M) 크기의 초콜릿들이 N개 생긴다.

(1*M) 크기의 초콜릿은 열(M) 기준으로 자르면 (M-1)번 자르게 되는데 N개 있으므로 N번 반복해야 한다.

위의 과정을 정리하면 (N*M) 크기의 초콜릿은 총 (N-1) + (M-1)*N = N - 1 + M*N -N = M*N - 1번 자르게 된다.

N, M = map(int, input().split())
print(N*M-1)

통계를 복습해볼수 있는 쉬운 문제지만 sys를 통해 입력을 빠르게 받지 않으면 시간초과가 뜬다. 

# 시간초과 때문에 정답률이 낮은 것 같다.

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

from collections import Counter
import sys

li = []
for _ in range(int(input())):
    li.append(int(sys.stdin.readline()))
li.sort()
ave = round(sum(li)/len(li)) # 산술평균
if len(li) % 2 == 1:
    median = li[len(li)//2]
else:
    median = round((li[len(li)//2-1] + li[len(li)//2])/2) # 중앙값
cnt = Counter(li)
cnt_sort = cnt.most_common()
max_cnt = cnt_sort[0][1]
max_cnt_li = []
for c in cnt_sort:
    if c[1] == max_cnt:
        max_cnt_li.append(c[0])
if len(max_cnt_li) > 1:
    mode = max_cnt_li[1] 
else:
    mode = max_cnt_li[0] # 최빈값
li_range = max(li)-min(li) # 범위
print(ave)
print(median)
print(mode)
print(li_range)

if X % 3 == 0: 
    X //= 3 
elif x % 2 == 0: 
    X //= 2 
else: 
    X -= 1~~~~

단순하게 위와 같은 방식으로 풀면 틀린다. 예를 들어 10 같은 경우 10 -> 5 -> 4 -> 2 -> 1 보다 빠른 

10 -> 9 -> 3 -> 1이 있기 때문이다.

2 또는 3으로 나누어 떨어지는 수더라도 그 수에 1을 빼준 값도 같이 다음 단계로 넘겨주는 식으로 해결했다.

X = int(input())
cnt = 0
li = [X]

while(1 not in li):
    t = []
    for x in li:
        if x % 3 == 0:
            t.append(x//3)
        elif x % 2 == 0:
            t.append(x//2)
        t.append(x-1)
    li = t
    cnt += 1
print(cnt)

길이가 1인 수는 9개 있고. (1, 2, 3... 9) 길이가 2인 수는 90개 있고, 길이가 3인 수는 900개가 있다. 

길이가 n인 수는 총 9 * 10**(n-1) + 9개 있다는 점을 감안해서 풀면 쉽다.

N = int(input())
n = 9
a = 1
ans = 0

while(N != 0):
    if N - n > 0:
        ans += a*n
        N -= n
        n = n*10
        a += 1
    else:
        ans += a*N
        break
    
print(ans)

입력을 그냥 받으면 시간 초과가 걸린다. sys를 통해 빠르게 입력을 받아주자.

import sys

n = int(input())
s = 0
for _ in range(n):
    s += int(sys.stdin.readline())
print(s-n+1)

조합 문제이다.

단순히 조합을 계산하고 뒤에 0의 개수를 새면 시간 초과가 걸리기 때문에 효율적인 방법을 찾아야 된다.

아래의 코드가 처음에는 이해가 잘 안될수도 있다. 예시를 들어 풀다 보면 이해가 더 잘 될 것이다.

n, m = map(int, input().split())

def cnt2(n):
    n2 = 0
    while(n != 0):
        n //= 2
        n2 += n
    return n2

def cnt5(n):
    n5 = 0
    while(n != 0):
        n //= 5
        n5 += n
    return n5

print(min(cnt2(n)-cnt2(m)-cnt2(n-m), cnt5(n)-cnt5(m)-cnt5(n-m)))

소수 관련 문제는 아리토스테네스의 체 방식을 사용하면 효율적으로 풀 수 있다. 

종종 보게 될 알고리즘이니 기억해두면 좋을 것 같다.

n = int(input())
li = list(map(int, input().split()))
t_li = [1]*(max(li)+1)
for i in range(2, max(li)//2 + 1):
    if t_li[i] == 1:
        for j in range(i+i, max(li)+1, i):
            t_li[j] = 0
prime = []
for i in range(2, len(t_li)):
    if t_li[i] == 1:
        prime.append(i)
cnt = 0
for n in li:
    if n in prime:
        cnt += 1
print(cnt)

math.sqrt를 통해 제곱근을 구할 때 완접제곱수라면 결괏값의 맨 끝은 항상 0이 나오는데

이 점을 활용해서 문제를 풀었다.

EX) math.sqrt(4) = 2.0

import math

li = []
for i in range(int(input()), int(input())+1):
    if str(math.sqrt(i))[-1] == '0':
        li.append(i)
if len(li) > 0:
    print(sum(li))
    print(li[0])
else:
    print(-1)

간단한 수학 문제이다.

7 -> 12 -> 22 -> 35 ... -> 처음에는 7 다음에는 10 그다음에는 13을 더하는 패턴이다.

add라는 변수를 7에서 시작해서 3을 더하면서 ans에다 계속 더해주면 된다.

ans = 5
add = 7
for i in range(int(input()) - 1):
    ans += add
    add += 3
print(ans%45678)

이미지에 필터를 돌린다는 느낌으로 범위를 설정하고 각 모서리의 값들이 같은지 확인하면 된다.

# ok는 break 용도

N, M = map(int, input().split())
m = min(N, M)
li = []
for _ in range(N):
    li.append(list(map(int, list(input()))))
ok = False

for l in range(m, 0, -1):
    if ok:
        break
    for i in range(N+1-l):
        if ok:
            break
        for j in range(M+1-l):
            if li[i][j] == li[i+l-1][j] == li[i+l-1][j+l-1] == li[i][j+l-1]:
                ans = l
                ok = True
                break
        
print(ans**2)

정렬하고 풀면 쉽다.

N = int(input())
M = int(input())
li = sorted(list(map(int, input().split())))
ans = 0
s, e = 0, len(li)-1

while s != e:
    if li[s] + li[e] == M:
        ans += 1
        e -= 1
    elif li[s] + li[e] < M:
        s += 1
    elif li[s] + li[e] > M:
        e -= 1
        
print(ans)

기본적인 다이나믹 프로그래밍 문제이다.

n = int(input())
li = [list(map(int, input().split())) for i in range(n)]
if n > 1:    
    li[1][0] += li[0][0]
    li[1][1] += li[0][0]
    for i in range(2, n):
        for j in range(i+1):
            if j == 0:
                li[i][0] += li[i-1][0]
            elif j == i:
                li[i][j] += li[i-1][j-1]
            else:
                li[i][j] += max(li[i-1][j], li[i-1][j-1])
print(max(li[-1]))

그리디 알고리즘 문제이다. 정렬을 사용하면 쉽게 풀 수 있다!

lambda를 사용해 끝나는 시간과 시작하는 시간 순으로 두 번 정렬해주는 게 핵심이다. 

li = [list(map(int, input().split())) for _ in range(int(input()))]
li.sort(key=lambda x : (x[1], x[0]))
cnt = 1
end_time = li[0][1]
for i in range(1, len(li)):
    if li[i][0] >= end_time:
        cnt += 1
        end_time = li[i][1]
print(cnt)

최소공배수는 최대공약수를 안다면 쉽게 구할 수 있다.

-> 최소공배수 = a * b // a와 b의 최대공약수

최대공약수는 유클리우드 호제법을 통해 쉽게 구할 수 있다.

# 유클리우드 호제법은 이런 종류의 문제를 풀 때 자주 사용하게 되므로 기억해놓으면 좋다.

for _ in range(int(input())):
    a, b = map(int, input().split())
    a, b = max(a, b), min(a, b)
    s = a*b
    
    while(b != 0):
        n = a%b
        a = b
        b = n
    
    print(s//a)