[BOJ] 12월 3-4주차
BOJ 16953: A → B
BOJ 16951: 블록 놀이
Link : https://www.acmicpc.net/problem/16951
solution
이게 왜 브루트 포스지? 라는 생각이 처음에 들었는데, 잘 보면 브루트 포스로 풀 수 있다.
처음에 왜 저런 의문이 들었는가 생각해 봤다. 그냥 첫 항에서 K씩 더해가면 되는거 아닌가 싶었는데
첫 항이 무슨 값인지 모르니까 이 값에 대해서 모든 경우의 수를 돌려줘야 하는거였다.
그래봤자 상한이 1000이므로 1부터 1000까지 다 돌려주면 된다.
BOJ 16968: 차량 번호판 1
Link : https://www.acmicpc.net/problem/16968
solution
브루트 포스에 속해있는 문제라서 브루트 포스로 풀어보려고 했는데 굳이 그럴 필요가 없어보여서 경우의 수를 계산해서 풀었다.
매우 간단하다. 문자는 26가지, 숫자는 10가지가 기본인데 연속됐으면 각각 25가지, 9가지가 추가될 수 있다.
길이가 4까지 이므로 재귀로 처리하는 것도 방법이다.
BOJ 17085: 십자가 2개 놓기
Link : https://www.acmicpc.net/problem/17085
solution
브루트 포스로 풀었다.
십자가가 놓인 자리를 chk에 표시하고 십자가를 뺄 때는 일일이 기록했던 위치를 다시 꺼내며 false로 바꾸다보니
어떻게 구현은 가능했지만 만약 맵의 범위가 조금 더 넓었거나 십자가의 갯수가 2개가 아니고 더 많아진다면
어림도 없이 메모리 초과를 받고 다른 방법을 모색했을 것 같다. 다만 이런 경우라면 충분히 재귀로 해결이 가능하다.
이것저것 조건에 맞춰서 예외 처리를 해주다보니 코드가 다소 복잡해보이지만 로직은 간단하다.
십자가는 중심부로부터 사방으로 1칸씩 커지고 십자가 크기가 1씩 증가하면 Size 역시 4씩 증가하므로
십자가가 놓일 수 있는 상태일 때 현재 사이즈를 이전 값에 곱해준 상태로 인자를 넘겨 재귀 호출한다.
십자가가 2개가 됐을 경우 답의 후보가 되므로 최댓값이 되는지 체크해주고 함수를 종료한다.
BOJ 17088: 등차수열 변환
Link : https://www.acmicpc.net/problem/17088
solution
브루트 포스 문제인줄 알고 무턱대로 덤볐는데 N이 $10^5$까지 커질 수 있는걸 보고 뭔가 심상치 않았다.
커팅을 엄청 열심히 해야하나? 가능한가? 이런저런 생각을 하면서 설명을 읽었는데 각 원소마다 케이스가 3개다.
$3^{10^5}$인데 이게 정말로 가능한건가? 싶었는데 카테고리를 보니 DP로 풀 수 있었다.
카테고리를 보고 시작하는 나를 반성하면서.. 안심하고 DP로 풀었다.
일단 수열이 모두 등차수열이 되도록 하려면 인접한 원소들 사이의 차 즉, 공차(d)가 모두 같아야 한다.
그래서 a[0], a[1]에 연산을 해주는 케이스 9개를 만들어주고(dx[], dy[]) 각 케이스별로 픽스된 d에 대해서
2번째부터 탐색을 진행하면서 연산을 해주거나 안해주는 케이스 3가지(dt[])에 대해 2번째에서도 공차가 d와 같으면
다음 순번으로 재귀를 돌려주도록 했다.
풀고나니까 solved.ac에 브루트 포스 알고리즘 탭이 뜨는걸 확인할 수 있었다.
브루트 포스로도 풀 수 있는 문제구나 싶어서 궁금해서 찾아봤는데 방식은 비슷한 것 같다.
커팅하는 방식도 비슷한 것 같고.. 이렇게 풀 수 있는데 왜 나는 그렇게 생각을 하지 못했는지 아쉽다.
1문제 푸는데 뒤통수를 2번은 얻어 맞았다. 오늘도 또 하나 배우고 간다. 😂
BOJ 17135: 캐슬 디펜스
Link : https://www.acmicpc.net/problem/17135
solution
구현 문제.
궁수가 어느 위치에 있을지 모르므로 next_permutation으로 모든 경우의 수를 돌려줬고
궁수가 쏘는 범위를 탐색하는덴 BFS를 썼다. 또 시간 단축을 위해 가지치기를 좀 해줘야 한다.
조건에 맞춰서 구현을 해야하는데, 궁수들이 같은 턴에 쐈을 때 가지치기를 해주는게 좀 까다로웠다.
같은 턴에 궁수 1이 처치한 적이 궁수 2가 가장 먼저 만나면서 가장 왼쪽에 있는 적이라면 역시 같은 적을 처치해야 하는데
bool 타입만으로는 같은 턴(round)인지 체크해줄 수 없어서 killed[x][y]에 round를 표시해주기로 했다.
그리고 앞서 말한 시간 단축을 위한 가지치기는 chk[x][y]를 이용했는데, 거쳐간 자리라면 나아갈 수 있는 횟수를 적어놓도록 처리했다.
만약 d=5이고 해당 칸을 1번만에 도달했다면 앞으로 4칸을 더 갈 수 있으므로 chk[x][y]=4가 되는 셈이다.
이 때 다른 경로에서 해당 칸에 3번만에 도달했다면 2를 적어줘야 하는데 앞서 지나간 경로가 현재 경로보다
더 나아갈 수 있으므로 커팅해줬다.
적을 처치했다면 궁수는 더 이상 행동을 할 수 없으므로 break문으로 BFS를 종료하도록 처리했다.
고려해야하는 부분이 좀 많다.
TC만 체크하고 통과했다면 구현을 아주 잘한게 아닐까 생각이 든다. 반례를 찾느라 생각 외로 시간이 오래 걸렸다.
BOJ 17136: 색종이 붙이기
Link : https://www.acmicpc.net/problem/17136
solution
구현 문제.
설명을 잘 읽어야 한다. 색종이는 종류별로 5개가 존재한다.
이 점을 잘 이용해서 커팅하면 시간 제한에 걸리지 않고 AC를 받을 수 있다.
각 위치에서 가장 크게 붙일 수 있는 색종이의 크기 값을 전처리해서 attachMax[x][y]에 담아주고 시작한다.
전처리를 해줌으로써 solve()로 재귀 호출할 때마다 만나는 모든 좌표에 대해서 색종이 크기의 상한을 체크할 필요가 없어진다.
지금 생각해보니까 딱히 전처리를 할 필요는 없어 보인다. 그냥 색종이를 놓을 수 없는 위치를 발견했을 때 바로 break문으로
빠져나오도록 해도 상관이 없을 것 같다. 나름의 편의를 위해 전처리를 해줬는데 시간만 더 먹는 상황인듯.
상당히 구현이 까다로울 줄 알았는데 비슷한 난이도의 구현 문제들에 비해 꽤 깔끔하게 짤 수 있다.
그래도 설계를 해보기 전까지는 모르는거라서(..) 구현 문제는 마주치면 피하고 싶어진다.
이 문제는 삼성 A형 기출인걸로 아는데 카카오도 그렇고 구현 문제가 정말 많이 나오는 것 같으니
합격하기 전까지는 덤벼보는 멘탈도 기르는게 필요할 듯 하다.
BOJ 1074: Z
Link : https://www.acmicpc.net/problem/1074
solution
3달 전에 도전했다가 틀렸던 분할 정복 문제. 드디어 풀었다!
여태까지 풀어왔던 문제들에 비하면 난이도가 낮다고 생각하지만(..) 어차피 내가 못푸는건 못푸는거라 😥
오랜만에 틀린 문제중에 이 문제는 풀어봐야겠다 싶어서 설명을 읽었는데 대충 어떻게 해야할지 감이 왔다.
개인적으로 약한 분할 정복 파트지만, 어쨌거나 분할 정복도 재귀로 처리하는 거니깐 이라는 마음가짐으로
도전하니까 방법을 떠올리는데 그렇게 어렵지 않았다.
코드가 조금 복잡한데, 왜 그런가 생각해보니 사각형의 범위를 행에서 위아래로, 열에서 양쪽으로 나눠서 그런 것 같다.
이 문제의 경우 어차피 재귀가 놓여져 있는 모습을 보면 알겠지만 정해진 순서대로 재귀를 돌아야 한다.
때문에 위 코드처럼 사각형의 바운더리를 임의로 처리해줄 필요가 없고, 기준점 하나만 잡고 크기를 조절해 간다면
훨씬 간단하게 짤 수 있다. (물론 방식은 위 코드와 비슷하다)
모든 케이스를 모두 재귀를 돌린다면야 답은 나오겠지만 TLE를 받게된다.
때문에 인풋으로 받은 좌표(r, c)가 범위 내로 들어오지 않는다면 커팅해줘야 한다.
BOJ 16948: 데스 나이트
BOJ 16920: 확장 게임
Link : https://www.acmicpc.net/problem/16920
solution
BFS 유형인데 조금 특이하다.
각 영역별로 큐를 관리하면서 돌리는 방식으로 구현해야 TLE를 피할 수 있었는데
자세한 내용은 여기를 참고하자.
BOJ 16932: 모양 만들기
Link : https://www.acmicpc.net/problem/16932
solution
BFS 문제.
1이 인접한 것들을 묶음으로 묶어서 넘버링을 해주고 각 묶음의 크기 또한 체크해주자.
이후 0인 블럭들에 대해서 BFS를 돌려주는데, (해당 블럭과 인접한 묶음들의 크기 합)+1의 최댓값을 출력하면 된다.
BOJ 16947: 서울 지하철 2호선
Link : https://www.acmicpc.net/problem/16947
solution
DFS + BFS 문제.
사이클을 찾는데 DFS를 이용하고 사이클까지의 거리(답)를 구하는덴 BFS를 이용한다.
BOJ 16973: 직사각형 탈출
Link : https://www.acmicpc.net/problem/16973
solution
BFS 문제.
직사각형을 통째로 원하는 위치까지 벽에 부딪히지 않고 움직여야 한다.
직사각형 면적 모두를 체크할 필요는 없어보여서 테두리만 조건에 위배되는지 체크해줬다.
BOJ 4803: 트리
Link : https://www.acmicpc.net/problem/4803
solution
Union-Find 문제.
입력받는 값들을 서로 같은 집합으로 묶어주는걸로 시작한다.
그럼 각 집합이 트리인지 여부를 체크헤야 하는데, 집합에 속해있는 임의의 정점에서 출발했다고 했을 때
탐색해온 점 중 중복되는 경우가 발생하면 이는 트리가 아니다. 즉, 사이클이 발생하면 안된다.
근데 나같은 경우 입력받는 정점 u, v에 대해서 서로 오갈 수 있도록 엣지를 설정해줬기 때문에
임의의 정점에서 출발했을 때 다시 출발점으로 돌아온다는 보장이 없다.
이 점이 집합 내의 사이클에 속한다는 보장이 없기 때문이다. 반례 참고
때문에 위에서 설명한 것처럼 중복되는 경우만 탐색하는건 무리가 있다고 생각이 들었다.
그래서 집합에 속한 정점의 수를 members[i]에 담았고, DFS로 탐색하면서 checkMembers[i]에 갱신되도록 해줬다.
탐색하는 과정중에 만약 members[i]보다 checkMembers[i]가 더 많아지게 된다면 중복해서 체크한게 되므로
이 집합은 트리가 아니게 된다. 따라서 isTree[find(i)]를 false로 설정해줬다.
(물론 find(i)는 i의 부모를 리턴하는 함수)
처음에 생각한 것보다 상당히 복잡하게 구현했다.
분명 더 간단한 코드로 풀 수 있을 것 같다는 생각이 든다.
BOJ 3108: 로고
Link : https://www.acmicpc.net/problem/3108
solution
Union-Find 문제.
다섯가지 명령이 있다고 해서 머리가 조금 아플 뻔했는데 입력을 보고 안심했다.
연필을 올린 횟수를 출력하면 되는데 처음에 연필이 내려져 있다는 점을 주의해야한다.
(x, y)좌표가 각각 하한이 -500에서 시작하므로 0부터 시작하도록 각각 500을 더해주고 시작한다고 하면
원점에서 500을 더한 (500, 500)에서 직사각형이 지나간다고 했을 때 이 경우는 카운트하지 말아야 한다.
이 부분만 주의한다면 크게 어려운 점은 없다. 연결돼 있는 사각형들의 집합의 갯수를 찾으면 된다.
댓글남기기