📌 AtCoder Beginner Contest 281

2022-12-10 일자 9시부터 10시 40분까지 진행된 실시간 대회에 참여했습니다.

이번에는 문제가 적절해서 빠르게 3solve 를 하였는데 D번은 접근이많이 어려웠던것 같습니다.
D번은 풀지못해서 따로 이번 블로그에서 풀이를 하지 않았지만 , 처음에는 itertools 의 combination 함수를 사용했으나 시간초과를 당했는데 , DP 알고리즘을 통해 풀수있다는걸 들었습니다.

DP를 알고있지만 어떤 문제가 나올때 그 문제에 대해 적절히 쓸수있다는것은 몇배는 어려운거같네요.

📌 A - Count Down

본문 링크

간단한 구현 문제입니다.
$N$ 이 주어지면 $N$ 부터 $0$ 까지 출력하는 문제입니다.

📌 A - Code

N=int(input())

while N!=-1:
    print(N)
    N-=1

📌 B - Sandwich Number

본문 링크

이번 대회에서 많이 맞왜틀을 한 문제입니다.
저도 2번틀리고 맞은 문제입니다.

문제는 간단합니다. 1~10 길이의 문자가 주어졌을때
가장 왼쪽에 대문자가 있고 , 그다음에 100000~999999 의 숫자가 있고 그 다음에 대문자가 있는 문자인지 아닌지 판별하는 문제입니다.

일단 저는 이 문제에서 조건을 총족하기 위해서는 문자열의 길이가 항상 8 이 되어야한다고 생각했습니다.
그리고 가장 왼쪽 문자와 가장 오른쪽문자가 대문자일때 중간의 문자가 int 형으로 변환시 100000~999999 인지 판별해주었습니다.

하지만 사람들이 가장 많이 틀린이유는 파이썬의 int형 변환입니다.

String="0100000" 이 문자를 int 로 바꾸면 어떻게 될까요?
신기하게도 $100000$ 이 나옵니다. 즉 파이썬은 str 자료형을 int 로 변환할때 앞에 0이 있으면 그냥 무시해줍니다.
따라서 문자열 길이가 8이 아니라는 조건을 쓰지않고 단순히 가장왼쪽문자열과 가장오른쪽문자열이 대문자이면 중간의 문자를 int 형으로 변환할시 A0100000A 라는 반례가 생깁니다.

📌 B - Code

S=input()

answer=0
if len(S)==8:
    if 65<=ord(S[0])<=90 and 65<=ord(S[-1])<=90:
        S=S[1:]
        S=S[:-1]
        try:
            S=int(S)
            if 100000<=S<=999999:
                answer=1
        except:
            print("No")
            exit(0)

if answer==1:
    print("Yes")
else:
    print("No")

📌 C - Circular Playlist

본문 링크

$N$ 은 입력의 길이 $T$ 는 시간이 주어집니다.
리스트의 값은 노래 하나를 듣는데 걸리는 시간을 의미합니다.

$T$ 가 600 초가 일때 리스트의 노래를 순차적으로 듣습니다.
180 초가 소모되는 노래를 듣고 240 초가 필요한 노래를 듣고 120 초가 필요한 노래를 듣습니다.
만약 이때 한바퀴를 다 들었음에도 $T$ 값이 남는다면 다시 처음부터 듣습니다.
따라서 한바퀴를 다 돌면 540 초가 걸려 $T$ 는 60 이 되고 첫번째 노래에서 $T$ 는 0 이 되버립니다.
그러므로 출력은 인덱스 위치 1 과 노래를 듣기 시작해서 $T$ 가 0 이될때까지 시간 - 60 이 출력하게 됩니다.

문제에서 범위를 보자면

• $1≤N≤10^5$ , $1≤T≤10^1$$^8$ , $1≤A_i≤10^9$

입니다.
즉 완전탐색을 하면 시간초과가 날 수 있습니다.
간단하게 생각해보니깐 굳이 매번 돌 필요가 없고 , $T$ 에다가 리스트의 합을 나눈 나머지를 구하면 $O(N)$ 으로 $T$ 가 0이 되는 지점을 찾을수 있습니다.

📌 C - Code

N,T=map(int,input().split())

L=list(map(int,input().split()))
K=sum(L)

T=T%K

for i in range(N):
    if T>=L[i]:
        T-=L[i]
    else:
        print(i+1 ,T)
        break

✅ 후기

Atcoder 에서 D번은 한번 풀어보고싶었는데 시간이 많이 있었음에도 풀지못한게 조금 아쉽습니다.
처음에 시간초과를 받아서 리스트의 나머지 값들을 활용해볼려고 접근은했지만 DP를 사용하지는 않았습니다.
그래도 이번에는 A~C번을 빨리 풀어서 다른문제를 풀 시간이 1시간 넘게있었습니다.

이번 대회에 참가하여 레이팅이 43 이 올랐습니다. $Brown$ 을 달성할때까지 열심히 대회참여를 해볼생각입니다.