AtCoder Beginner Contest 354 upsolving

WooHyunLEE·2024년 5월 18일

어제 처음 코드포스 Div.2 1솔하고 레이팅 440받고 슬퍼하던것도 잠시, 첫 앳코더도 2솔 레이팅 24로 마감했다..

그래도 업솔빙하면 계속 더 좋아질거라 생각하고 앞으로는 문제를 읽고 못 푼 문제까지 업솔빙하려고 한다.

A - Exponential Plant

코드포스 div.2 A번에 비하면 선녀가 다름없었다.
그냥 log2(h+1) + 1 하면 끝나는 문제

제출한 AC코드

import sys
import math

input = sys.stdin.readline

h = int(input())

print(int(math.log2(h+1)) + 1)

B - AtCoder Janken 2

이 문제 역시 주어진 요구사항대로 rating을 더하주다가 이름을 사전순대로 정렬 후 사람인원수만큼 mod연산을 해주면 끝난다.

제출한 AC코드

import sys

input = sys.stdin.readline

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

for _ in range(n):
    name, rate = input().split()
    arr.append((name, int(rate)))

arr.sort()

t = 0

for name, rate in arr:
    t += rate
winner = t % n
print(arr[winner][0])

C - AtCoder Magics(upsolving)

처음 문제만 보고는 생각보다 쉬워보였는데 내 알고리즘 실력을 쉽지않았다.. N의 조건이 2≤N≤2×10**5 였기때문에 완전탐색은 안 될거같았고, cost를 기준으로 내림차순을 한 뒤 배열에 0번째 값을 빼고 다시 strength를 기준으로 오름차순 정렬하여 이분탐색을 생각해 문제를 풀려하였고, 문제에서 제시된 3개의 예시는 맞았지만 WA가 나오게되었다.

처음 제출한 오답코드

import sys
import bisect

input = sys.stdin.readline

n = int(input())

ans = [i for i in range(1,n+1)]

arr = []

for i in range(1,n+1):
    strength, cost = map(int,input().split())
    arr.append((strength, cost, i))

arr.sort(key=lambda x:(-x[1]))
temp = arr.copy()
for i in range(n):
    if len(temp) == 0:
        break
    strength,cost,num = temp.pop(0)
    cnt = [x[0] for x in temp]
    cnt.sort()
    if bisect.bisect_right(cnt, strength) != len(cnt):
        ans.remove(num)
print(*ans)

~~다시 제출해보니 TLE가 맞았다.~~

풀이를 보고 나니 간단한 정렬문제인것을 깨닫고 좌표같은 문제가 나오면 x,y축으로 생각해 좌표를 찍어보는 것도 좋을거같다 생각했다.

정답코드

import sys


n = int(input())

arr = []
ans = []

for i in range(1,n+1):
    a,b = map(int, input().split())
    arr.append((a,b,i))

arr.sort()
min_cost = int(1e9)
for x,y,i in arr[::-1]:
    if y < min_cost:
        min_cost = y
        ans.append(i)
print(len(ans))
print(*sorted(ans))

strength 기준으로 정렬 후 reverse하여 for문을 순회하면서 낮은 cost를 정답 배열에 넣어주면 된다.
X,Y축으로 생각하면