[20250215]Atcoder Beginner Contest 393

 

점수: 600 [3 / 7]
등수: 6987 / 10700

 

 

문제별 풀이

A - Poisonous Oyster

from collections import deque
import sys, itertools, math, heapq

ip, op = sys.stdin, sys.stdout

ret = {"sick fine": 2, "sick sick": 1, "fine sick": 3, "fine fine": 4}
op.write(f"{ret[ip.readline().rstrip()]}\n")

• 문제요약: 입력 받는 문자열의 종류에 따라 알맞은 숫자를 출력
• 의도: 매우 간단한 경우의 상황을 조건에 따라 해결이 가능한가?
• 접근 방법: 딕셔너리를 이용해 문자열에 대한 값을 가져오는 아이디어를 사용
• 다른풀이: 일반 if문을 사용한 조건 처리
• 개선점: 입력이 적을 때는 input() 함수 사용

B - A..B..C 

from collections import deque
import sys, itertools, math, heapq

ip, op = sys.stdin, sys.stdout

S = ip.readline().rstrip()
n, ret = len(S), 0
for i in range(1, n//2+1):
    for j in range(n - (3 + (i-1)*2) +1):
        if S[j] == 'A' and S[j + i] == 'B' and S[j + 2*i] == 'C':
            ret += 1
        
op.write(f'{ret}\n')

• 문제요약:문자열에서 일정한 간격으로 A-B-C가 성립하는 인덱스 모음의 갯수 세기
• 의도: 조건에 맞게 반복문을 변형하여 사용가능한가 혹은 완전탐색으로 생각 가능한가
• 접근 방법:
  • 일정한 간격의 3문자 이므로 간격의 길이가 문자열 길이의 반보다 클 수 없는 것을 이용하여 경우의 수를 줄이고
  • 3 문자의 간격의 길이에 따라 조건을 맞춰 주어 반복문을 변형하여 푼다
• 다른풀이: (i,j,k) 세 인덱스의 모음을 완전탐색하여 풀 수 있다.
• 개선점: 입력이 적을 때는 input() 함수 사용
• 시간복잡도: O(n^2)

C - Make it Simple

from collections import deque
import sys, itertools, math, heapq

ip, op = sys.stdin, sys.stdout
n, m = map(int, ip.readline().split())
graph = [set() for _ in range(n+1)]
ret = 0
for _ in range(m):
    a, b = map(int, ip.readline().split())
    if a == b or b in graph[a]:
        ret += 1
        continue
    graph[a].add(b)
cnt = 0
for a in range(1, n + 1):
    for b in list(graph[a]):
        if a in graph[b]:
            cnt += 1
    
op.write(f'{ret + cnt//2}\n')

• 문제요약: 자기자신으로 돌아오는 간선과 다중 간선 제거하기
• 의도: 그래프를 구현하고 조건에 맞는 처리가 가능한가?
• 접근 방법:
  •  u == v인 경우 갯수 세주는 변수에 +1 해주기
  • 모든 정점을 돌면서 다중간선있는지 확인하기
• 다른풀이:
  다중간선 확인할 때 u->v의 방향을 통일 시켜 중복되는 것만 세주는 방법으로 이후의 따로 그래프를 도는 로직제거 가능.
• 개선점: 그래프에서 중복을 체크할 때 가중치가 같으면 방향을 바꾸는 아이디어 생각하기
• 시간복잡도: O(n+m)

D - Swap to Gather

Can't Solve

E - GCD of Subset 

Can't Solve

F - Prefix LIS Query

Can't Solve

피드백 & 회고

1. 잘한점
   1. cp 처음으로 시도를 했다
   2. 앞으로 채워나갈 부분 확인
2. 아쉬운점
   1. 문제를 해석하는 시간이 많이 걸렸다
   2. 대회 코드작성 환경을 기존과 다른 부분이 있어 시간 소모가 많았다.
3. 다음 목표
   1. D 난이도 공략을 위해 낮은 문제 구현 전략 설정하기
   2. D 난이도의 문제를 풀기 위해 백준 골드 난이도 문제 풀기

 

 

[현재: 그레이,  목표: 브라운,  제한시간: 2025년 3월 14일]