[BOJ] 4~5월 문제풀이

BOJ 20056: 마법사 상어와 파이어볼

Link : https://www.acmicpc.net/problem/20056

solution

구현 문제.
구현 난이도는 시리즈에 비해 낮은 편이다.
근데 구현 문제가 그렇듯이 습관에 발목잡히면 참 답이 없다.
continue를 곳곳에 걸어놔서 clear()가 안먹히는 케이스가 있어가지고 고치는데까지 정말 오래걸렸는데
실전에서 이런 실수 안하도록 정말 주의해야겠다. 🥺

BOJ 20057: 마법사 상어와 토네이도

Link : https://www.acmicpc.net/problem/20057

solution

구현 문제.
토네이도 이동 방향과 방향에 따라 토네이도의 영향에 닿는 부분을 설정해주는게 포인트다.
전자는 약간의 연산으로 좀 간단하게 구현이 가능한데 후자 또한 가능할걸로 보이지만
어떻게 해야할지 직관적으로 안떠올라서 그냥 하드코딩했다.
요구하는 내용이 그렇게 어렵진 않으니 잘 구현해주자.

BOJ 20058: 마법사 상어와 파이어스톰

Link : https://www.acmicpc.net/problem/20058

solution

구현 문제.
구역별로 돌린 후 모든 위치에서 녹는 얼음을 조사한 후 해당되면 녹이면 된다.
구역별로 나누는건 그렇다 치고 이걸 어떻게 돌릴까 하다가 그냥 테두리로 쪼개서 돌리기로 했다.
시간 제한에 구애받을 정도의 최적화가 필요없어 난이도가 낮다.
개인적으로 삼성 기출 문제 풀면서 깔끔하게 푼 느낌이라 뭔가.. 좋았다(?)

BOJ 2156: 포도주 시식

Link : https://www.acmicpc.net/problem/2156

solution

간단한 DP 문제.
f(p, cnt) : 인덱스 p에서 연속으로 cnt개를 골랐을 때 마실 수 있는 최대 양
11달 전 아무 것도 모를 때 어떻게 꾸역꾸역 구현을 해서 맞기는 했었는데
시험끝나고 돌아와보니 저격을 당했는지 시간 초과로 바뀌어서 다시 풀었다!
상당히 간단한 문젠데도 약간 삐걱삐걱거리는게 많이는 못풀어도 자주 건드려야 겠다.

BOJ 13305: 주유소

Link : https://www.acmicpc.net/problem/13305

solution

간단한 그리디 문제.
특정 위치 A에 있고 A에서의 가격을 cur이라 했을 때, 뒤에 cur보다 작은 가격을 취급하는 위치 B가 있다고 하자.
그러면 B에 도착했을 때 그 전까지의 거리(sumDist)를 cur과 곱한 값을 결과값에 더해주면 된다.
이후엔 cur이 위치 B에서의 가격으로 재설정되도록 해주고, sumDist 역시 초기화해주자.

BOJ 3273: 두 수의 합

Link : https://www.acmicpc.net/problem/3273

solution

투 포인터 문제.
입력받은 값들을 정렬해준 후 처리한다.
두 수의 합이 x보다 크고 작은지에 따라 범위를 어디서 조여올지를 결정하는데,
정렬된 값이므로 합이 x보다 작거나 같으면 값이 커져야 하므로 i를 증가시키고
그렇지 않으면 j를 감소시킨다.

중복된 값들이 존재하면 위 방법으로 조건에 맞는 순서쌍을 온전히 취하기 어렵다고 생각해서
겹치는(중복되는) 값들은 cnt[value]에 카운팅해주고 활용했다.

BOJ 17406: 배열 돌리기 4

Link : https://www.acmicpc.net/problem/17406

solution

구현 문제.
맵 전체 크기가 50*50이고 들어오는 순서 길이도 6이어서 최적화를 고민할 필요는 없다.

시계 방향으로 1칸씩 돌아가므로 좌측 상단을 기준으로 해서 반시계 방향으로 swap을 해주도록 하자.
그러면 최종적으로 시계 방향으로 1칸씩 돌아간 모양이 되는데, 정사각형 내부를 일일이 구현해주는건
하드코딩에 가깝다고 생각했고 복잡할 것 같아서 재귀로 가운데 (r,c)에 도달할 때까지 처리하도록 했다.
순서 길이가 k인데 모든 경우의 수를 고려해야하기 때문에 next_permutation()으로 처리했다.

BOJ 17471: 게리맨더링

Link : https://www.acmicpc.net/problem/17471

solution

구현 문제.
모든 구역에서 2가지 팀중 하나를 선택하는 경우의 수를 모두 고려한다. (총 $2^n$가지, divide())
n개의 구역에 대해서 나눠진 선거구에 대해 속한 구역들이 모두 연결됐는지 여부를 테스트한다. (search_connected())
속한 2개의 팀(선거구)에 대해 테스트가 모두 끝났다면 답을 갱신해준다.
답이 갱신되지 못한 경우 INF로 값이 남아있기 때문에 이 때는 -1을 출력하도록 한다.

BOJ 17281: ⚾

Link : https://www.acmicpc.net/problem/17281

solution

구현 문제.
결정된 순서는 첫 이닝부터 끝 이닝까지 유지된다는 점을 주의하자.
당연히 그렇지 않을줄 알고 열심히 풀어보려고 하다가 시간복잡도가 $(8!)^N$이 나와서 포기했다가
결정된 순서가 끝까지 유지된다는걸 알게되고 다시 풀었다. (이 경우 시간복잡도는 $8! \times N$)
대부분의 구현 문제가 그렇듯이.. 함수별로 처리하는 영역을 잘 분리시켜서 잘 구현해주자.
나같은 경우 main에서 next_permutation()으로 순서가 되는 모든 경우의수를 고려해줬고,
perm()에서 각 이닝마다 matching()을 호출해 정해진 순서해서 얻을 수 있는 점수를 얻어온다.
그렇게 모든 이닝이 끝나면(inning > n) 답을 갱신해준다.
이 때, 반환값에는 들어가지 않지만 startTurn이라는 전역 변수에 다음 이닝 때 시작할 위치를 계속 넣어줬다.

perm()은 사실 permutation을 줄여서 이름을 지었는데 이것저것 뜯어 고치다가 순열 내용이 main 바깥으로
나가버렸다😅 혹시 코드를 보는 분이 있다면 순열과 관계없으니 그냥 DFS라고 생각해주시길..

BOJ 17472: 다리 만들기 2

Link : https://www.acmicpc.net/problem/17472

solution

구현 + 섬 번호 결정(DFS or BFS) + MST 문제.
주어진 섬들의 번호를 결정해주는데 DFS나 BFS를 통해 결정해준 후,
각 섬 번호를 각 vertex처럼 생각했을 때 섬과 인접한 바다에서 정해진 방향으로 나아갔을 때 만나는 섬과의 거리
들을 모두 d[s][e]에 저장해주자. (물론 여러 경우가 생길 수 있으므로 최솟값을 저장해야 한다)
그렇게 섬과 섬 사이의 최소 거리가 정해졌으므로 MST 알고리즘을 활용하면 된다.

n과 m의 범위도 그렇고 사실은 MST를 쓰지 않아도 풀 수 있다고 생각했다.
지금도 그 생각은 변하진 않았으나 생각보다 구현하는데 시간도 오래걸리고 어느 반례에서 걸리는지 도통 모르겠어서
브루트포스로는 포기하고 위의 방법대로 다시 고쳐서 결국 AC를 받았다.
알고리즘을 더 쓰는 대신 풀이가 깔끔하다는 장점이 있지만, 실전에서는 외우지 못했다면 사용 못한다는 단점도 있다.
요즘 게을러져서 푸는데 시간이 너무 오래걸렸다. 의욕적으로 할 필요가 있어보인다🥺

생각보다 많이 풀지 못했다🥺
중간고사 시험기간부터 과제도 많아지고 시간이 많이 들어가면서 문제 풀 시간이 많이 없었다.
원래는 원래는 5월 쯤 올라갈 글이었지만.. 폴더 구석 어딘가에 넣어두고 깜빡했었다😮
앞으로 달마다 문제풀이 글을 올릴 정도로 시간적인 여유가 있을지 모르겠지만 노력해봐야겠다!