rope = []
for i in range(0, n):
    rope.append(int(input()))

rope.sort(reverse=True)
max_w = 0
for cnt, r in enumerate(rope):
    if max_w <= r * (cnt + 1):
        max_w = r * (cnt + 1)

print(max_w)

반복문을 돌면서 (로프의 개수) * (지금 확인한 로프의 무게)의 값이 저장해 놨던 무게 max_w 보다 크면 max_w를 바꿔준다.

dynamic programing으로 접근해 보면 조약돌의 오른쪽에서 작업을 시작하여 각 자리마다 그 때의 최소 작업 횟수를 저장하여 memoization할 수 있다.

하지만 단순히 이전까지의 최소 작업 횟수에 현재 자리의 최소 작업을 더한다고 최종적인 최소 작업 횟수가 될 수는 없다. 아래와 같은 예를 보자.

조약돌의 개수가 위와 같이 주어졌을 경우 두 번째 자리까지 최소 횟수는 2이다. 이를 저장하고 다음으로 넘어가서 마지막 자리인 두 개의 조약돌을 빼내는 횟수 1을 단순히 더하면 총 횟수는 3회이다.

하지만 처음부터 1번 작업으로 모두 진행하게 되면 두 번 만에 끝낼 수 있다.

from queue import PriorityQueue

n = int(input())
pq = PriorityQueue()

for _ in range(n):
    num = int(input())
    pq.put(num)

result = 0

while pq.qsize() > 1:
    tmp = pq.get()
    num = pq.get()
    result += tmp + num
    pq.put(tmp + num)

print(result)

우선순위 큐에 입력으로 들어온 카드 뭉치의 크기를 삽입하고 반복문을 시작한다.

우선순위 큐의 첫 번째, 두 번째 원소를 빼내서 더해준다 (카드 뭉치를 합침). 그리고 이를 결과가 저장될 result 함수에 저장해준다 (합칠 때 비교한 횟수를 반영). 마지막으로 첫 번째와 두 번째 원소의 합을 다시 우선순위 큐에 넣어준다. 다시 넣어주면 합쳐진 카드 뭉치를 자연스럽게 다시 합칠 수 있다.

| 1 | 4 | | 6 | 1 | | 2 | 5 | | 4 | 2 | | 3 | 6 | | 7 | 3 | | 4 | 2 | | 1 | 4 | | 5 | 7 | | 2 | 5 | | 6 | 1 | | 3 | 6 | | 7 | 3 | | 5 | 7 |

여기서 첫 번째 리스트(성적 순)는 면접 순위가 가장 높은 사람이 나올 때까지 슬라이싱을 하여 set으로 만들어 준다. set(p_cnt[1:top2 + 1])

반대로 두 번째 리스트(면접 순)는 성적 순위가 가장 높은 사람이 나올 때까지 슬라이싱을 하여 set으로 만들어 준다. set2 = set(p_cnt2[1:top1 + 1])

이렇게 만들면 각 set에 한 분야의 1 순위인 사람보다 다른 분야의 순위가 높은 사람들을 걸러낼 수 있고, 이 둘의 교집합을 이용하면 두 분야의 1 순위인 사람들보다 적어도 하나의 분야의 순위가 높은 사람들을 추려낼 수 있어서 정답을 구할 수 있다고 생각했다.

예를 들면 55-50+40+90-100+10-11 이라는 수식이 입력됐을 때 55-(50+40+90)-(100+10)-11 = 55-50-40-90-100-10-11 로 만들 수 있다.

st = input().strip()+ '+'
total = 0
minus = False
num = ''
for c in st:
    if c.isdigit():
        num += c
    else:
        if minus:
            total -= int(num)
        else:
            total += int(num)
        if c == '-':
            minus = True
            
        num = ''
print(total)

입력은 숫자와 부호가 섞인 문자열로 주어지기 때문에 그 문자열을 확인하면서 문자가 숫자인지 부호인지에 때라 다르게 처리를 해주어야 한다.

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 $2^31-1$보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

끝나는 시간을 기준으로 먼저 정렬하고 같으면 시작하는 시간을 기준으로 정렬하는 것이 핵심이다.

이렇게 정렬을 하게 되면 항상 그 시간에 시작하는 회의 중 가장 빨리 끝나는 회의를 선택할 수 있으며, 끝나는 시간 이후에 시작하는 회의 중 가장 빨리 끝나는 회의도 바로 선택할 수 있다.

n = int(input())
meetings = []

for _ in range(n):
    s, f = map(int, input().split())
    meetings.append((s, f))

meetings.sort(key=lambda x: (x[1], x[0]))

cur = 0
cnt = 0
for s, f in meetings:
    if cur <= s:
        cur = f
        cnt += 1
print(cnt)

입력

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 ’.’, ’#’, ‘O’, ‘R’, ‘B’ 로 이루어져 있다. ’.’은 빈 칸을 의미하고, ’#‘은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, ‘O’는 구멍의 위치를 의미한다. ‘R’은 빨간 구슬의 위치, ‘B’는 파란 구슬의 위치이다.

입력되는 모든 보드의 가장자리에는 모두 ’#‘이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

출력

최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

맵을 BFS로 탐색하면서 시뮬레이션 하는 문제이다.

처음 시도한 방식은 정말 단순하게 모두 다 구현하는 것으로 맵 리스트 자체에서 구슬들을 실제로 움직이는 것까지 구현하였다.

제한

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

풀이

2부터 증가하면서 제곱 수의 배수들을 빼주는 식으로 제곱 ㄴㄴ 수를 찾아가는 방식으로 문제를 해결하려 다음과 같이 시도하였다.

첫 시도의 문제점

n, m = map(int, input().split())
sqr = [False] * (m - n + 1)
cnt = 0
for i in range(2, int(m ** 0.5) + 1):
    j = 1
    sqr_num = i ** 2
    while sqr_num * j <= m:
        if sqr_num * j < n: pass
        elif not sqr[sqr_num * j - n]:
            sqr[sqr_num * j - n] = True
            cnt += 1
        j += 1
print((m - n + 1) - cnt)

def dp(b1, b2, n, m):
    global memo
    if b1 == n:
        return 1
    cnt = 0
    for i in range(b2 + 1, min(m, b2 + m - n + 1) + 1):
        if (b1 + 1, i) in memo:
            cnt += memo[(b1 + 1, i)]
        else:
            tmp = dp(b1 + 1, i, n, m)
            cnt += tmp
            memo[(b1 + 1, i)] = tmp
    return cnt

t = int(input())
for _ in range(t):
    memo = {}
    n, m = map(int, input().split())
    print(dp(0, 0, n, m))