이번에는 공군 동아리에서 개최한 보라매컵에 참여했다. (예선)
아쉽게도 이번엔 배경이나 뱃지를 주지 않았다.
🏆 대회에서 푼 문제
참가자 280명 중 31등을 했다.
문제 시간은 3시간 정도 주어졌지만 나는 늦게 시작해 1시간 정도 풀었다.
🧩 A. 특식 배부
치킨이 남는 경우 X개의 치킨을 먹고, 치킨이 부족한 경우 N개의 치킨을 먹는다.
단순히 min(A, N) + min(B, N) + min(C, N) 이다.
🧩 B. 출입 기록
출입부를 dict형태로 작성하고, 기본적으로 밖에 있다고 봐야 한다.
그리고 이상개수를 세면 되는데,
이상 개수는 다음과 같을때 하나씩 증가시키면 된다.
1. 출입부에 들어온 기록이 없는데 나간 경우 (들어온 기록 누락)
2. 출입부에 들어와 있는데 또 들어왔다고 한 경우 (나간 기록 누락)
3. 입력이 끝난 후 들어와 있는 경우 (나간 기록 누락 : 문제에서 마지막 상태에는 모두 나갔다고 했다.)
🧩 C. 시간 외 근무 멈춰!
이 문제는 쉬운 문제였지만 고민을 많이 했었다.
평시 근무 스택과 시간 외 근무 스택 2개를 준비해서 그리디 방식으로 넣어주면 해결된다.
(나는 실제로 스택을 만들지는 않았다. 문제에서는 최소 시간 외 근무 일수만 요구했기 때문이다.)
모든 작업의 마감기한은 다르지만 시작시간은 모두 같기(처음 부터) 때문에 단순히 정렬도 필요 없이 순서대로 진행하면 된다.
평시 근무를 하는것이 우선순위이기 때문에, 평시 근무 스택에 넣고 작업단위를 쪼갤 수 있으니 마감기한까지 넘치면 시간 외 근무 스택에 넣자.
🧩 D. 잠입
처음에는 단순히 bfs문제인줄 알았다.
0 matrix가 주어지고 레이저를 배치하고 주인공을 움직이려고 했었다.
하지만 이내 단순한 문제라는 것을 알게되었다.
로봇이 있기 때문이다.
로봇은 주인공 보다 한발 늦게 같은 위치에서 출발하는데, 레이저의 영향을 받지 않는다.
즉, 주인공은 로봇에게 따라잡히지 않으려면 레이저 때문에 돌아가는 무빙을 보이면 안된다.
최대한 왼쪽으로 붙어서 가는데, 레이져에 맞지 않으면 된다.
단, 이 문제는 좀 분기가 많다.
레이저가 같은 행에 2개가 들어갈 수 있기 때문이다.
아래와 같이 6개의 분기를 고려해야 한다.
마지막 케이스를 고려하지 못해 한번 틀렸었다.
📖 혼자 풀어 본 문제
🧩 E. 조교의 맹연습
이 문제는 시간이 좀 더 있었으면 대회 때 풀 수 있었을 것 같다.
좌로 돌아를 1, 우로 돌아를 3, 뒤로 돌아를 2로 하는 dp 문제라고 할 수 있다.
dp는 (k, 4)크기로 정의하고 k번 순회하며 세 경우의 수를 모두 고려해나가면 O(K)만에 풀 수 있다.
🧩 F. 통신소
bfs문제다. 여기서 부턴 에디토리얼을 보고 풀었다.
레이더끼리 겹치는 구간이 있다는 것이 문제이고 이것을 해결하는 것이 핵심이다.
처음에는 그래서 max 힙을 이용해 세기가 큰 신호부터 먼저 이동하게 했고, visited 배열에 방문 체크를 했었다.
하지만 이렇게 하면 O(NMlog(NM))가 걸려서 대략 최대의 수를 넣으면 207,913,442가 나와서 1초에 해결할 수 없다.
결국 O(NM)의 방식을 찾아야 한다.
답은 간단했다. 신호의 최대 세기가 3,000이니 1~3,000 까지의 deque를 만들어서 큰것부터 사용하면 O(NM)가 걸리게 된다.
정말 신박하고 재밌는 풀이였다.
🧩 G. 전투기 출격
전투기의 최적 이동 비용에 대해선 플루이드 워셜을 이용하면 쉽게 구할 수 있다.
문제는 그 다음인데, 여기선 동료 전투기의 출발 위치, 도착 위치 를 적절히 구해야 한다.
변수가 2개라 브루트포스 방식으로 하면 O(N^2)로 너무 커진다. 적어도 O(NlogN)이 나와야 할 것이다.
여기서 풀이를 생각해내지 못했는데, 그래프를 그려보면 착륙 비용 때문에 요동치게 된다.
그래서 이분탐색을 적용하지 못했다.
하 지 만 드라군이 출동하면 어떨까?
농담이고;; 출발 위치에 따라 착륙 비용이 요동치기 때문에 출발 위치를 고정하면 해결되는 문제였다.
이후 도착위치에 따른 연료는 증가 그래프를 그리기 때문에 lowerbound를 구하면 해결된다.
'프로그래밍 > 코테 회고' 카테고리의 다른 글
AI Network Scholarium I 회고 (0) | 2023.03.19 |
---|---|
제2회 곰곰컵 회고 (0) | 2023.01.09 |
2022 서울사이버대학교 프로그래밍 경진대회 (SCUPC) 회고 (0) | 2023.01.02 |
코테 회고 작성기 (0/10) (0) | 2023.01.02 |