[BOJ] 3월 문제풀이
BOJ 1783: 병든 나이트
Link : https://www.acmicpc.net/problem/1783
solution
그리디 문제.
세로 길이에 따른 케이스 분류를 잘해줘야 한다. (물론 가로도 마찬가지긴 하다)
n이 2일 때 조금 고생을 했지만 문제 난이도는 실버5일 정도로 어렵진 않다!
BOJ 12919: A와 B 2
BOJ 11728: 배열 합치기
Link : https://www.acmicpc.net/problem/11728
solution
투 포인터 문제.
각 배열 정렬 후 인덱스를 나눠 작은 값부터 하나씩 뽑아 출력한다.
BOJ 10825: 국영수
BOJ 17143: 낚시왕
Link : https://www.acmicpc.net/problem/17143
solution
(상어를 물고기로 잘못읽어서 변수가 fish로 돼있습니다)
구현 문제.
낚시왕이 마지막 열에서 도착하고 물고기를 잡는 행위까지 했다면 끝남에 유의.
물고기 이동시 한 칸씩 이동하면 TLE를 받음에 유의. 언제 제자리(같은 방향으로)로 돌아오는지 체크.
구현할 내용이 크게 많지는 않으나 스스로 유의미한 TC를 만들어 보기가 힘든 케이스라고 생각된다.
때문에 정확하게 구현을 했는지에 초점을 두는게 중요해 보인다.
나같은 경우 낚시왕이 열을 한 칸씩 탐색하도록 바깥 for문에서 돌려주었고 (즉, cur이 현재 탐색 열)
설명에 제시된 바와같이 현재 열에 속한 물고기를 먼저 잡도록 했다. (단, 죽은 물고기는 체크 안함에 주의)
그리고 물고기가 이동되도록 하는데, 두마리 이상의 물고기가 같은 위치에 겹치게 될 경우
가장 크기가 큰 물고기가 존재하도록 적절히 처리해주자.
BOJ 17140: 이차원 배열과 연산
Link : https://www.acmicpc.net/problem/17140
solution
구현 문제.
적힌 설명대로 구현하면 되나 대부분 구현 문제가 그렇듯이
실수할 여지가 많으니 주의하기.
BOJ 17142: 연구소 3
Link : https://www.acmicpc.net/problem/17142
solution
브루트포스 문제.
지금까지 푼 연구소 시리즈답게 브루트포스로 풀 수 있다. 다만 시간이 좀 빡빡하다.
맵 내에 빈 칸이 모두 바이러스가 되는 경우 답을 갱신하도록 해야한다.
이미 바이러스이지만 처음에 선택받지 않은 바이러스를 살아있는 갯수(alive)에 카운팅되지 않도록 주의.
어떤 바이러스가 선택되는지에 대해 DFS로 처리했는데(select_virus()) 이전값을 나타내는 인자(prev)가
시간복잡도를 낮추는데 도움을 줄 수 있으니 체크하자.
(만약 바이러스가 상한인 10개가 존재하고 m개를 골라야한다고 가정할 때 고르는 경우가 ${}_n \mathrm{ C }_r$이 돼야지
$10^m$이 되면 안된다. 자잘한 팁이지만 이 부분을 적절하게 처리 못해서 TLE를 받았다.)
내용 구현은 크게 어렵지 않다. 기본 BFS 문제와 크게 벗어나지 않는다.
BOJ 17779: 게리맨더링 2
BOJ 17837: 새로운 게임 2
Link : https://www.acmicpc.net/problem/17837
solution
구현 문제.
파란 벽을 만나고 방향을 바꿨을 때 케이스를 따져줘야 함에 주의.
흰색, 빨간색이면 위에 있는 말들도 같이 움직여야함. (순서는 색에 따라 맞춰서)
단, 방향은 기준이 되는 말만 바뀌고 나머지는 유지.
BOJ 17822: 원판 돌리기
Link : https://www.acmicpc.net/problem/17822
solution
구현 문제.
설명된 내용을 착실하게 구현하면 된다.
평균을 낼 때 그 값이 몫이 아님에 주의하자. (sum/cnt를 double로 처리해야 함)
BOJ 17825: 원판 돌리기
Link : https://www.acmicpc.net/problem/17825
solution
DFS 문제.
중복되는 케이스를 없애줘야 TLE도 면하고 답도 구할 수 있을줄 알았는데, 그게 아니었다.
visited로 걸러주지 않아도 시간 내에 들어오면서 충분히 답을 낼 수 있었다😂
시간복잡도를 고려하지 않고 (재귀 문제는 습관적으로 안해서 할 수 있을진 모르겠지만) 달려들어서
당연히 visited를 써줘야겠다고 생각한게 삽질의 원인이었다. 심지어 써주면 틀린다.
어느 걸러지는 케이스가 유의미하기 때문에 그렇다는건데.. 정확히 어느 부분이 문젠진 감이 안온다.
보다 구체적인 케이스를 위해서 인자를 추가해야 하는지, 그렇다면 무슨 인자를 추가해야할지도 모르겠다.
수련이 부족하다😩
BOJ 20061: 모노미노도미노 2
Link : https://www.acmicpc.net/problem/20061
solution
구현 문제.
쌩 구현 문제라서 딱히 설명할건 없지만.. 어쩌다보니 코드가 굉장히 길어졌다.
줄이는건 줄이는건데 실전처럼 조급한 상황에서 줄일 자신은 없을 것 같고 실수 여부가 중요할 것 같다.
첫 제출때 WA를 받았는데 범위 체크를 잘못한게 원인이었다. 이거 찾는데만 45분..
구현은 구현 나름대로 재밌지만 반례찾는게 고역인듯 하다. 실수하지 말자!
BOJ 19236: 청소년 상어
BOJ 19237: 어른 상어
Link : https://www.acmicpc.net/problem/19237
solution
구현 문제.
설명하는 조건들을 적절히 구현해주면 된다.
꼭 주의해야할 요인은 딱히 없었떤 것 같다.
BOJ 19238: 스타트 택시
Link : https://www.acmicpc.net/problem/19238
solution
구현 문제.
요구 조건 적절히 구현하기. 딱히 주의할 점은 없다.
연습하기 좋은 문제.
BOJ 20055: 컨베이어 벨트 위의 로봇
Link : https://www.acmicpc.net/problem/20055
solution
구현 문제.
구현이 어렵진 않다. 문제 설명이 더 어렵다.
hongju님의 글에서 설명만 참고했다.
문제 설명 읽어보고 테스트 케이스 아웃풋이 이해가 안가면 위 링크로 가보는걸 강추.
댓글남기기