SW 역량 테스트 준비 - 문제
문제 목록 : https://code.plus/course/34
풀지 않았던 문제들만 풀어보며 기록했습니다.
시뮬레이션
BOJ 14499: 주사위 굴리기
Link : https://www.acmicpc.net/problem/14499
solution
처음에 문제 설명이 이해가 안가서 좀 애먹었는데
만약 TC에서 출력이 왜 그렇게 나오는지 알았다면 푸는데까지는 그렇게 어렵지 않다.
주사위가 동서남북으로 굴러갈 때 각 값이 어디로 이동해야 하는지만 안다면 적당히 구현해주면 된다.
BOJ 14891: 톱니바퀴
Link : https://www.acmicpc.net/problem/14891
solution
문제 설명을 따라서 그대로 구현만 하면 된다. 별도로 설명할게 없다.
다만 TC 출력을 처음에 계속 틀려서 뭐가 문젠지 계속 찾아봤는데 적어보자면
처음에 회전할 톱니바퀴의 번호와 방향을 각각 n_0, dir이라고 했을 때
n_0, dir이 먼저 회전되고 이웃한 톱니바퀴는 회전된 n_0 톱니바퀴의 N, S극을 기준으로 회전하는줄 알았다.
그래서 당연히 큐에다 넣고 돌렸는데 계속 엉뚱한 답이 나왔었다..
사실은 회전된 상태가 기준이 되지 않고 아무것도 회전하지 않은 초기 상태에서
n_0부터 이웃된 톱니바퀴로 나아가면서 회전할지 하지 않을지 여부를 체크한 뒤
마지막에 모조리 처리를 해주어야 한다.
BOJ 15662: 톱니바퀴 (2)
Link : https://www.acmicpc.net/problem/15662
solution
위에서 풀었던 BOJ 14891: 톱니바퀴에서 톱니바퀴 갯수와 출력 내용만 다르다.
적절히 수정해주면 된다.
BOJ 14503: 로봇 청소기
Link : https://www.acmicpc.net/problem/14503
solution
뭔가 BFS처럼 보이는 문제지만 현재 위치와 주변 상태를 가지고 1개의 위치만 컨트롤하기 때문에
단순한 구현 문제라고 볼 수 있겠다. 문제에서 제시한 대로 착실하게 구현하면 된다.
BOJ 14890: 경사로
Link : https://www.acmicpc.net/problem/14890
solution
지켜야 할 조건이 조금 많다. 구현의 묘미는 모든 조건을 빠뜨리지 않도록 꼼꼼히 체크해야하는 점인거 같다.
짜는 동안 구현해야하는 부분중 일부를 머릿속으로만 생각하다가 잊어버려서 나중에 애를 좀 먹었다.
한 행 혹은 한 열을 양쪽으로 스위핑하면서 모든 조건을 통과하면 지나갈 수 있는 길로 체크했는데
어렵진 않지만 행과 열을 드나들다보니 좀 헷갈린다. 인덱스를 잘못 적어놔서 이 부분에서도 많이 틀렸다.
전체적으로 구현이 어렵다는 느낌보다는 실수할 여지가 많다는게 더 짚이는 문제.
BOJ 3190: 뱀
Link : https://www.acmicpc.net/problem/3190
solution
개인적으로 난이도에 비해 구현이 빡셌다. 코드가 길어져서 그런 생각이 들었나 싶기도 하다.
head, tail을 제외한 부분을 body라고 하면 기본적으로 움직이는 방향은 선발대인 head의 기록을 따라간다.
꼬리가 없는 상태에서 사과를 1개 먹으면 tail이 생성되며, 그 다음부터는 body가 생성되는 식이다.
body와 tail을 분리시킨 이유는 head가 특정 time이 돼서 방향을 바꿀 때 맵에 방향을 기록하도록 했는데,
나같은 경우 사과를 먹으면 기존의 body, tail은 값을 유지하도록 하고 이전 head의 위치를 body에 업데이트 하는 방식을 취했다.
이렇게 하면 body에 업데이트되는 녀석은 push_back 되는 바람에 맨 뒤에 위치하게 되고 tail보다 뒤에 위치한다.
맵에 기록된 L, D를 tail이 밟았을 때 없애도록 장치를 만들어놨는데 tail보다 뒤에 나오면 문제가 생길거 같다는 생각이 들었다.
때문에 body와 tail을 분리하도록 했고, 이 때문에 예외 처리가 좀 많아져 코드가 다소 지저분해졌다.
시뮬레이션 특성상 (난이도가 높지 않다면) 어느 정도 비효율성을 감안하기 때문에 AC받는 코드 유형이 다양해지는게
시뮬레이션 문제의 묘미라고 생각이 든다. 푸는데 좀 오래걸렸다. ㅠㅠ
BOJ 15685: 드래곤 커브
Link : https://www.acmicpc.net/problem/15685
solution
직접 TC를 분석해보면 규칙을 금방 찾을 수 있다.
이전까지 그린 방향을 역순으로 탐색하면서 시계방향으로 1번씩 돌려가며 이동하고
이동할 때마다 현재 위치를 표시해준다.
마지막엔 현재 위치를 포함해 오른쪽, 밑, 오른쪽밑(대각선) 총 4칸이 차있으면 값을 갱신해주면 된다.
BOJ 2933: 미네랄
Link : https://www.acmicpc.net/problem/2933
solution
클러스터를 통째로 컨트롤해야 하기때문에 각 점이 어느 클러스터에 속해있는지 표시하면서 진행했다.
각 턴이 돌아갈 때마다 어떤 클러스터가 밑으로 내려갈지 모르기 때문에 각 클러스터의 번호를 매번 부여해줘야 했다.
또한 각 클러스터가 얼마나 밑으로 내려가야 하는지를 체크하고 구현하는게 좀 까다로웠는데,
각 클러스터의 바닥에 해당되는 미네랄들이 밑으로 얼마나 내려가야하는지 모두 체크한 후 그 중 최솟값이
최종적으로 내려가야하는 거리라는걸 늦게 깨달아서 시간이 오래 걸렸다.
BOJ 3568: iSharp
BOJ 2290: LCD Test
Link : https://www.acmicpc.net/problem/2290
solution
각 숫자가 그려지는 패턴만 파악하면 되는 문제다.
어디가 반복되고 어느 기호가 입력받는 s에 대해서 영향을 받는지 파악하면 된다.
세로로 출력하는게 아니고 가로로 출력함에 주의.
브루트 포스
BOJ 15661: 링크와 스타트
Link : https://www.acmicpc.net/problem/15661
solution
BOJ 14889: 스타트와 링크와 사실상 같은 문제다.
위 문제에서는 N이 짝수로 주어지고 각 팀의 멤버 수가 동일하게 N/2로 나뉘게 된다.
하지만 이 문제에서는 각 팀 멤버 수가 1명 이상이고 짝수로 떨어진다는 보장이 없다.
총 인원수가 N이라고 하면 각 팀 멤버 수만 고려했을 때 나오는 경우의 수는 N-1가지이다.
[1, N-1], [2, N-2], … [N-2, 2], [N-1, 1]이 되는데 사실 가운데의 경우를 제외하고는 고려할 필요가 없다.
이 문제에서는 각 팀 멤버들의 시너지 합을 각각 r1, r2라 했을 때 |r1-r2|의 최소를 구해야 한다.
[1, N-1], [2, N-2] 등의 경우 |r1-r2|가 다른 케이스에 비해 더 크게 나올 수밖에 없다.
따라서 짝수의 경우 당연히 [N/2, N/2]를, 홀수의 경우 [N/2, N/2+1]을 고려하면 된다.
string에 담고 순열을 돌려 모든 케이스를 탐색하도록 했다.
BOJ 14502: 연구소
Link : https://www.acmicpc.net/problem/14502
solution
벽을 3개 세워 버이러스의 확산을 최대한 막아야한다. 단, 벽은 무조건 3개를 세워야 한다.
주목할 점은 세로, 가로의 상한선이 8이라는 점이다. 고려해야 할 케이스가 굉장히 적다.
모든 빈 칸(0)에 대해서 벽을 3개 세우기 위해 3중 for문을 이용해도 문제없다. 즉, 브루트 포스로 풀면 된다.
BOJ 15683: 감시
Link : https://www.acmicpc.net/problem/15683
solution
세로, 가로의 상한선이 굉장히 적다. 효율성을 크게 따질 필요가 없는 구현 문제에 속한다고 보면 되겠다.
이 문제가 조금 까다로워질 수 있는건 같은 종류의 CCTV도 각각의 방향이 독립적으로 행동돼야 한다는 점이다.
그리고 다행히도 CCTV는 최대 8개까지만 설치된다. 때문에 맘놓고 재귀로 마지막 CCTV까지 넘어가도록 짤 수 있었다.
solve()는 마지막 CCTV에 도달했을 때 답을 갱신하는데, 만약 맵에 CCTV가 없을 경우 예외처리를 해줘야 한다.
예전에 구현 문제 유형을 찾아보면서 시도했다가 풀지 못한 문제라 좌절했던 기억이 나는데 이번엔 풀어서 다행이다!
BOJ 15684: 사다리 조작
Link : https://www.acmicpc.net/problem/15684
solution
단순한 브루트 포스 문제다. 시간 제한에 거의 걸친 상태로 아슬아슬하게 풀었다.
해당되지 않는 조건은 깔끔하게 가지치기를 해주는게 기본인데 사실 그렇게까지 하지 않아도 풀리는 문제도 꽤 많다.
다만 이 문제의 경우 (내가 푼 것처럼 짰다면) 가지치기를 해주지 않으면 TLE를 면하기 힘들어 보인다.
구현 문제가 다 그러하듯이 문제 설명에 충실해 짜주면 되지만 생각보다 고려하지 못하는 부분들이 종종 있다.
이 문제에서는 내가 놓은 다리가 옆의 다리와 연결되는지 또는 허공에 다리를 놓는지 꼭 체크해줘야 한다.
이미 놓은 곳에 다리를 놓는다면 WA를 받을 가능성이 높다.
BOJ 2210: 숫자판 점프
Link : https://www.acmicpc.net/problem/2210
solution
상하좌우를 돌면서 만들 수 있는 모든 경우의 수를 구하는 문제.
6자리만 채우면 돼서 BFS로 돌리고 중복 여부는 맵으로 처리했다.
BOJ 3019: 테트리스
BOJ 4902: 삼각형의 값
Link : https://www.acmicpc.net/problem/4902
solution
구현하기가 생각보다 빡센 문제다.
크기별로, 위치별로 만들어질 수 있는 모든 삼각형을 고려하면서 그 합을 구해야 하는데 이 부분이 좀 까다로웠다.
N의 범위가 명시돼있지 않은 상황에서 임의로 배열을 선언해서 시도하는건 무의미하다고 생각해서
결론적으로는 힙처럼 각 레벨에 인덱스들이 속하도록 하고 이를 수식으로 처리해줘야 했다.
놓치기 쉬운 부분이 있는데 역삼각형도 고려해줘야 한다. 이게 좀 까다롭다.
시간 초과를 받는다면 인덱스를 하나씩 탐색하며 더하고 있을 확률이 높다.
부분합으로 빠르게 구해주자.
BOJ 2916: 자와 각도기
Link : https://www.acmicpc.net/problem/2916
solution
범위가 적기도 하고 만들어질 수 있는 값이 [0, 360)이어서 브루트 포스로 풀 수 있는 것 같다.
유의할 점은 같은 각을 여러 번 이용할 수 있고, 380의 경우 20으로, -20의 경우 340으로 만들어줘야 한다.
BOJ 2422: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데
BOJ 14225: 부분수열의 합
Link : https://www.acmicpc.net/problem/14225
solution
최대 20자리밖에 안돼서 비트마스킹으로 처리했다.
테마에 딱 맞는 브루트 포스 문제. DFS로 풀어도 되고 딱히 설명할게 없다.
BOJ 16197: 두 동전
Link : https://www.acmicpc.net/problem/16197
solution
위치가 서로 다른 동전 2개가 주어지고 단 1개만 빠지도록 하는 최소 이동 횟수를 구해야 한다.
두 동전이 같은 방향으로 동시에 이동한다는 점이 이 문제의 특징이며
각 동전이 이동됐을 때의 상황을 케이스별로 나눠서 처리해야 한다. 가짓수가 많지 않다!
최소 이동 횟수를 구하는 문제여서 BFS로 풀었고 생각보다 구현이 쉬운 편이었다.
BOJ 16198: 에너지 모으기
Link : https://www.acmicpc.net/problem/16198
solution
선택된 원소를 제거하면서 진행하는데 특화된 자료형과 메소드가 있었다면 더할 나위 없겠지만
나는 그런 자료형을 몰라서 N도 10까지밖에 안늘어나니 브루트 포스로 해결했다.
BFS
BOJ 15653: 구슬 탈출 4
Link : https://www.acmicpc.net/problem/15653
Solution
코드가 너무 길어서 접었다(..)
이 문제는 BOJ 13460: 구슬 탈출 2에서 움직이는 횟수가 10번 이상일 경우 -1을 출력하는
조건만 사라진 상태라서 이전에 썼던 코드 중 1줄만 지워서 AC를 받았다.
(전에 풀면서 너무 고생했던 기억이 나서 처음부터 짜기가 싫었다)
움직인 횟수가 10회 이상일 때 while문을 빠져나오도록 하는 줄만 삭제했는데 통과할 수 있었던 이유는
빨간 구슬을 구멍으로 빼낼 수 없는 상황이 되려면 지나갔던 위치를 계속 도는 경우만 존재하므로(무한 루프)
이 케이스는 중복을 체크하는 조건문(chk)에서 탈락이 되기 때문에 다시 큐로 들어가지 않는다.
따라서 계속 돌려주면 큐가 비게되고 마지막에 -1을 출력하게 된다.
나중에 시간이 되면 줄을 좀 줄여봐야겠다. 너무 길다..
BOJ 5213: 과외맨
Link : https://www.acmicpc.net/problem/5213
solution
문제 설명이 엄청 길다. 놀랍게도 절반 이상이 푸는데 필요없는 내용이다!
행 번호가 홀수인지 짝수인지에 따라서 놓을 수 있는 타일 수도 다르고 놓이는 블록의 바운더리도 다르다.
전형적인 BFS지만 생각보다 까다롭다.
마지막으로 도달한 타일 번호를 END번이라 하면 직전에 있었던 타일 번호를 PREV[END]에 저장하고
시작점까지 역으로 도달하면서 답을 만들면 된다.
다른 타일로 옮겨갈 때에는 인접한 블럭의 수가 서로 같아야 하고 같은 타일이면 상관없음에 유의하자.
마지막 줄의 마지막 타일로 이동할 수 없는 경우가 존재할 수 있다. 이 경우에는 번호가 가장 큰 타일로 이동하면 된다.
나같은 경우 이 말이 이해가 안가서 qna, 다른 분들의 풀이를 참고하면서 알아봤는데
도달할 수 있는 타일 중에 번호가 제일 높은 타일로 이동하라는 말임을 알게됐다. (위 코드에선 target이 해당됨)
어차피 마지막 줄 반대편의 타일이 가장 높은 타일 번호이므로 어쨌거나 도달 가능한 가장 높은 번호의 타일을 찾으면 되겠다.
BOJ 3184: 양
Link : https://www.acmicpc.net/problem/3184
solution
영역별로 있는 양과 늑대의 수를 파악해 답을 갱신하는 문제. DFS 풀이.
BOJ 3187: 양치기 꿍과 아예 같은 문제.
BOJ 5014: 스타트링크
Link : https://www.acmicpc.net/problem/5014
solution
현재 위치에서 위로 U, 아래로 D만큼 움직일 수 있고 G층까지 도달할 수 있는 최소 횟수를 출력하는 BFS 문제다.
변수가 딱히 많지 않아서 구현하는데 어렵지 않다.
2번 TC를 검토해보면 알겠지만 이동하려는 층이 F층을 넘으면 안된다. 당연히 0층 이하로도 이동할 수 없다.
이 점만 유의한다면 쉽게 통과할 수 있다.
BOJ 12886: 돌 그룹
Link : https://www.acmicpc.net/problem/12886
solution
BFS라는 컨셉으로 풀긴 했으나 A, B, C가 갈 수록 값이 어떻게 변할지 가늠이 가지 않았었다. (생각이 짧았었다)
때문에 중복을 체크하는 chk를 정적인 배열로 선언해 O(1)만에 처리하는 일반적인 방법말고 map을 사용했다.
map으로 중복을 체크해도 풀리긴 풀린다. 시간 제한이 2초여서 넉넉하게 돌아간다.
(넘겨주는 자료형에 따라 달라질 수 있는데 640ms부터 1168ms까지 나왔었다. 정말 무식하게 풀었다)
이렇게 오래걸릴리 없다고 생각이 들어서 찾아보고 정리를 해서 코드를 고쳤더니 16ms까지 받을 수 있었다.
위 코드는 수정된 코드이며 수정한 부분에 대한 아이디어는 다음과 같다.
1. 수정하려는 대상 X, Y에 대해서 작은게 X고 큰게 Y라면 각각 X+X, Y-X이다. 변화량이 0이다.
즉, 총합은 일정하게 유지된다.
2. A, B, C가 주어졌을 때, 종류마다 '몇 개'가 있는지 궁금하지 어떤 '종류'인지는 알 필요가 없다.<br>
즉, 순서가 중요하지 않다는 말이다. 때문에 정렬을 통해 항상 값을 오름차순으로 유지하자.
3. 위의 1, 2번을 종합하면 SUM = A+B+C라고 했을 때 항상 C=SUM-(A+B)를 의미한다.
값 2개가 정해지면 나머지 값은 정해진다는 말이다. 때문에 chk를 2차원 배열로 설정하면 된다.
4. 인풋으로 들어오는 A, B, C의 상한은 각각 500이다. 즉 SUM의 상한은 1500이 된다.
그러므로 chk[1501][1501]로 선언하면 메모리 상으로 문제가 발생하지 않는다.
BOJ 14442: 벽 부수고 이동하기 2
Link : https://www.acmicpc.net/problem/14442
solution
벽을 k개 이하로 부수면서 도착 지점으로 가는 최단 경로를 구하는 문제다.
일반적인 길찾기 문제처럼 BFS 구조를 유지하되 조금 다른점이 있는데 정리하면 다음과 같다.
벽을 부순 횟수는 다른 경로에 영향을 준다.
(x, y)로 도달하는 경로1, 경로2가 존재하고 각각 도달했을 때 벽을 부숴온 횟수가 a, b라고 하자. (a>=b)
BFS는 최단 경로를 취하므로 각각의 경로는 (x, y)에 최단 경로로 도착한다.
경로2가 경로1보다 먼저 도착한 상태라고 가정하면
이 때 벽을 더 많이(또는 같게) 부숴온 경로1은 경로2보다 벽을 더 부술 기회가 없으므로
이후에 벽을 부숴서 최단거리로 도착하는 경우를 놓칠 수 있으므로 업데이트하지 않는다.
반대로 경로1이 먼저 도착했다면 경로2가 벽을 덜 부쉈으므로 경로1의 흔적을 무시하고 나아가면 된다.
위 코드에서 chk[x][y]는 (x, y)에 도착했을 때 부숴온 벽의 갯수를 의미한다.
일반적인 BFS라면 중복 체크용으로 bool 타입으로 설정했겠지만 위의 내용을 반영하기 위해 int 타입으로 설정해줬다.
BOJ 1600: 말이 되고픈 원숭이
Link : https://www.acmicpc.net/problem/1600
solution
바로 위에서 푼 문제에서 풀었던 방법으로 풀어본다고 막 제출했다가 다 틀렸다.
하지만 주목해야할 점은 비슷하다. 위에선 벽을 부순 횟수였다면 여기선 말의 움직임 가능 횟수가 포인트다.
중복을 체크하는 배열을 잘 설정해야 하는데, 위 코드에서는 chk[x][y][k]로 설정했고
말의 움직임으로 이동할 경우 chk[nx][ny][k-1]을, 걸어갈 때는 chk[nx][ny][k]를 체크해주면 된다.
((nx, ny)는 다음으로 이동할 좌표를 말한다)
BOJ 10026: 적록색약
Link : https://www.acmicpc.net/problem/10026
solution
BOJ 1012: 유기농 배추와 같은 문제.
BFS로는 풀이가 떠오르지 않아서 DFS로 풀었다.
BOJ 2234: 성곽
Link : https://www.acmicpc.net/problem/2234
solution
DFS로 풀었다.
각 영역을 조사하면서 그 영역의 갯수 그리고 넓이(용량)의 정보를 얻는게 먼저다.
이를 위해서 DFS로 탐색하도록 했으며, 이 문제는 특이하게도 벽의 정보를 비트마스킹으로 처리해야 한다.
또한 벽을 1개만 제거했을 때 얻을 수 있는 가장 넓은 방의 크기를 얻기 위해 인접한 방의 정보가 있어야 한다!
영역밖으로 넘어가는 부분은 OOB(x, y)로 처리해 넘어가지 못하도록 했고,
그렇지 않은 경우엔 지나갔는지 중복 체크를 하기 전에 이동하려는 위치로 가는 길에 벽이 쳐져있는지 확인해준다.
쳐져있다면 다른 영역일 가능성이 있다는 뜻이므로 그 영역의 방번호와 현재 영역의 방번호가 다른지 체크해주자.
같으면 벽만 쳐져있는 같은 영역이므로 넘어가고, 다르다면 이미 담았는지 중복 체크를 해준 후 중복이 안되면 담아준다.
위의 과정을 통해 맵의 모든 영역을 탐색해 방의 갯수, 각 방의 넓이, 인접한 방의 정보를 얻었다.
벽을 1개 부숴서 가장 넓은 방의 크기를 얻는다는건 인접한 각각 다른 방들과 넓이를 합쳤을 때 최댓값을 구한다는 말이므로
각 방에서 인접한 방을 돌면서 넓이 합의 최대를 구해주면 되겠다.
BOJ 3197: 백조의 호수
Link : https://www.acmicpc.net/problem/3197
solution
일단은 BFS 문제인데, BFS만 이용해서는 시간초과를 피하기 힘들다.
Union-Find가 카테고리에 걸려있어서 이걸로 푸는게 가능한가 생각해보다 답이 안나와서 포기했고
계속 시간초과와 싸움을 하다가 결국엔 qna를 참고해서 이분 탐색으로 풀었다.
각 얼음이 언제 녹는지를 BFS를 통해 전처리하고 그 결과를 MAP에 저장한다.
그리고 백조를 BFS(다른 백조를 찾는 BFS)에 돌려야 하는데 MAP[x][y]의 값이 건널 수 있는 시간보다 크면
건널 수 없는 것으로 처리한다. 물론 건널 수 있는 시간은 이분 탐색으로 매번 정하도록 한다.
되게 쉽게 풀줄 알았는데 아침부터 엄청 애먹었다.
BOJ 12906: 새로운 하노이 탑
Link : https://www.acmicpc.net/problem/12906
solution
기본적인 BFS 접근과 똑같이 하면 된다.
현재 위치가 1번이라면 2, 3번에 블럭을 옮겨 담는 경우,
현재 위치가 2번이라면 1, 3번에 블럭을 옮겨 담는 경우,
현재 위치가 3번이라면 1, 2번에 블럭을 옮겨 담는 경우
매 케이스마다 총 6가지 경우의 수를 큐에 계속 넣어주면 된다.
다만 중복을 처리하는 부분이 다르므로 이 부분을 map으로 처리했다. (당연히 다른 방법도 존재함)
BOJ 14395: 4연산
BOJ 2151: 거울 설치
Link : https://www.acmicpc.net/problem/2151
solution
qna 반례를 찾지 않았다면 풀 수 있었을까 싶은 문제. 주의해야할 점이 많다.
일단 이 문제는 이동하는 위치마다 카운트하지 않으므로 가장 먼저 도착했더라도 최적 경로가 아닐 수 있다.
때문에 도착하는 경우의 수들 중 거울 설치 갯수가 최소가 되는 값을 취해야 한다. 다 돌아야 한다는 말이다.
문제를 대충 읽어서 ‘!’마다 무조건 거울을 설치하면 안된다.
거울은 45도 틀어진 상태로 설치가 되지만, 빛이 90도 또는 270도로 꺾여서 갈 수 있다.
visited를 bool 타입으로 사용한다면 visited[x][y][cnt][dir]로 설정하게 될텐데 cnt가 곧 visited가 되도록
int타입으로 설정하자. (설치 갯수가 50개를 넘지 않을거라 생각했는데 시원하게 WA를 받았다)
배울게 많았던 문제다. 물론 꼼꼼한 분들이라면 그냥 통과했을 가능성이 높다(..)
BOJ 16137: 견우와 직녀
Link : https://www.acmicpc.net/problem/16137
solution
설명만으로는 이해가 안갔던 문제다. 처음에 쭉 읽고나서 몇 가지 의문인 것들도 있고 막막하기도 했었다.
qna를 보면서 푸는데 도움이 됐던 (사실 문제를 잘 읽으면 다 있는) 추가 설명들은 다음과 같다.
1. 오작교는 반드시 1개만 설치할 수 있다.
2. 제자리에 있을 수 있다.
3. 설치할 오작교는 '설치한 시점으로부터' M번마다 재설치되는게 아니고
탐색을 시작하기 전에 처음부터 이미 설치되있다고 생각해야 한다.
(기본으로 설치된 오작교와 똑같다고 봐야 함)
N은 10까지 커질 수 있으므로 BFS를 여러번 돌려도 시간 초과를 받지 않을거라 생각이 들어서
오작교를 설치할 수 있는 곳마다 설치를 하고 BFS를 돌리면서 도달하는 최단 거리를 구해줬다.
다이나믹 프로그래밍
BOJ 14238: 출근 기록
Link : https://www.acmicpc.net/problem/14238
solution
이 문제 덕분에 5차원 배열은 처음 선언해봤다. ㄷㄷ
DP[길이][B의 개수][C의 개수][B 사용 가능 칸까지 남은 칸 수][C 사용 가능 칸 까지 남은 칸 수]<br>
로 설정했고 길이가 짧은 덕분에 메모리도 많이 먹지 않았다.
BOJ 12969: ABC 문제도 비슷하게 문자열을 다루는 DP 유형인데
못풀어서 풀이를 참고했던게 이 문제에 도움이 됐다.
특정 문자열이 조건을 만족하는지 여부만 체크하면 되기 때문에 캐시를 bool타입으로 설정해도 된다.
B 사용 가능 칸, C 사용 가능 칸까지 남은 칸 수는 조건에 맞춰서 사용시마다 각각 +1, +2이 되며
이외 문자를 사용할 시 해당 값이 0이 아니라면 0이 될 때까지 -1을 해줘야 한다. (0이 되면 문자를 쓸 수 있게 되니까)
B, C의 갯수는 B 또는 C를 사용할 때마다 카운트 해주면 된다.
점화식만 세운다면 딱히 어려울게 없다. 다만 bool 타입으로는 탑다운을 처음 짜봐서 신선한 경험이었다.
BOJ 12869: 뮤탈리스크
Link : https://www.acmicpc.net/problem/12869
solution
데미지를 입는 SCV가 3개 뿐이어서 경우의 수가 많지 않다!
다만 브루트 포스로는 TLE를 피할 수 없으니 DP로 풀어야 한다.
체력이 0 이하가 되는 경우 인덱스는 0 미만이 될 수 없기때문에 0으로 설정해주도록 하면서
데미지를 가하는 모든 경우의 수에 대해 재귀를 돌리면 된다.
BOJ 12996: Acka
Link : https://www.acmicpc.net/problem/12996
solution
강사 3명을 A, B, C라 할 때 각 앨범에 참여하는 경우의 수를 구하는 문제다. DP로 풀어야 한다.
f(앨범 수, A 기회, B 기회, C 기회) : A, B, C가 앨범을 고르는 경우의 수
기저 사례를 잘 설정해놓고 앨범을 선택하는 경우의 수를 모두 재귀로 돌려주도록 하자.
BOJ 2008: 사다리 게임
Link : https://www.acmicpc.net/problem/2008
solution
DP 문제.
현재 위치를 cur이라 한다면 이동했을 때 사다리는 cur-1, cur+1밖에 없다.
따라서 주변을 제외한 사다리를 고려할 필요가 없다. (재귀가 해결해줄 것임)
일단 점화식을 다음과 같이 세워줬다.
f(현재 위치, 마지막으로 건넌 다리 번호) : 현재 위치에서 도착지 b까지 가는데 드는 최소 비용
우선 인풋으로 다리(가로선)의 정보를 받을 때 각 다리에 번호를 매겨서 bridge[세로선 번호]에 담아줬다.
이렇게 담아준 다리의 정보들은 현재 위치에서 갈 수 있는 경우의 수에 대해 영향을 주게 된다!
다리의 번호를 1부터 시작하도록 하고, 시작점 a에서 0번 다리를 건넌걸로 시작하자.
그럼 a번 사다리에서는 위에서 말했듯이 a-1, a+1로만 이동할 수 있게된다.
이 때 이동하면서 있는 사다리로 갈지, 사다리를 만들어서 갈지 여부에 따라 케이스 분류를 해줘야 한다.
0번 사다리를 건넌 상태이므로 a-1번 사다리에 놓여진 다리나 a번에 놓여진 다리 중 1번 이상인 다리가 있으면
별도의 비용 없이 건너갈 수 있다. 있는지 여부는 canMove()를 통해서 찾아주도록 했다. (이분 탐색)
물론 사다리가 있든 없든 사다리를 만들어서 이동할 수도 있다. 이 때는 Y의 비용을 추가하고 이동한다.
만약 현재 위치가 cur인데 왼쪽으로, 오른쪽으로 가는 다리가 없다면 바로 갈 수 있으므로 0을 반환하도록 해주자.
기타
BOJ 12871: 무한 문자열
Link : https://www.acmicpc.net/problem/12871
solution
문자열 s, t의 길이가 같을 때까지 각각 반복해서 문자열을 완성해준 후
하나씩 비교하면서 같은지 여부를 확인한다.
추가 문제
BOJ 9944: NxM 보드 완주하기
Link : https://www.acmicpc.net/problem/9944
solution
DFS로 구현해주면 된다. 문제에서 요구하는 조건이 조금 특이해서 구현 문제지만 골드3으로 설정된 것 같다.
기본적으로 모든 빈 칸에서 DFS를 돌리는 방식으로 구현했다.
밟은 빈 칸의 수를 세는게 아니라 (첫 방향을 포함해) 몇 번의 방향 전환을 했는지를 찾아야 한다.
때문에 방향이 정해졌다면 벽 또는 지나온 칸을 만나기 전까지는 계속 나아가도록 구현을 해줘야 한다.
이 부분은 DFS 내부에 while문으로 처리해줬고, DFS가 끝난 후에는 다음 DFS에 영향을 주면 안되므로
다시 while문을 통해 지나갔던 길을 돌아오면서 visited[x][y] = false를 해줘야 한다.
(위 코드에서는 visited를 쓰지 않았다. 벽으로 표시해도 사실상 상관없어서 똑같이 처리해줬다.)
단, 기저 사례는 움직일 수 없는 상태여야 한다.
움직일 수 없다면 remain(밟을 수 있는 빈칸의 수)이 0일 때 cnt(방향 전환 횟수)를 반환하고
그렇지 않다면 0을 반환하도록 설정해주자.
이전에 비슷한 문제를 풀었어서 구현은 그렇게 오래 걸리지 않았는데..
어떤 반례에서 걸리는진 모르겠으나 계속 WA를 받아서 여러번 갈아치우고 겨우 AC 받았다.
BOJ 8982: 수족관 1
Link : https://www.acmicpc.net/problem/8982
solution
구현 문제. 문제 설명과 그림부터 풀기 싫게 생겼다. 😂
개인적으로 조금 삐그덕 댔던 부분은 주어진 좌표를 활용하는 부분이었다.
가령 바닥의 수평선분 (x, y)가 (3, 2), (4, 2)이 주어지면 이걸 이었을 때 가로 1칸을 차지해야 하는데
곧이 곧대로 좌표를 이용하면 a[3][2], a[4][2]를 쓰게되고 이건 1칸이 아니라 2칸을 쓰는거라서 골치아팠다.
여기서 문제가 생기면 바닥 바운더리를 의미하는 좌표값을 입력받아도 의미가 없다. 때문에 이 부분을 좀 고민했다.
좌표를 가지고 어떻게 장난쳐야 문제 설명에 있는 그림과 같은 정보를 가질 수 있을까 TC를 분석해보다가
어떻게 끼워맞출 수 있는 방법을 찾아냈다. 이를 처리하는 방법은 분명 다양하겠지만 나같은 경우 이렇게 처리했다.
TC 1번을 예로 들어보자. 먼저 각 열에 물이 얼마나 차있는지를 나타내야 한다.
일단 처음 주어진 좌표 5개를 그림에 표시해보면 다음과 같다.
왼쪽 그림은 문제 설명에 충실한 상태이고 오른쪽은 내가 처리한 방식을 나타낸 그림이다.
오른쪽처럼 0열, 1열에 채워지는 물의 양은 (1, 5), (2, 3)만 이용했다.
굳이 수직 선으로 이동하는 좌표의 정보를 반영할 이유가 없다. 그냥 바로 y값만큼 부어주면 된다.
다만 x는 열이 0번부터 시작하므로 1씩 줄여서 반영해야 한다.
또 주의할 점이 있다면 위와 다르게 서로 x좌표의 차이가 2 이상일 때는 그 사이의 열에도 같은 양을 부어야 한다.
(인풋에서 좌표 (3, 4), (5, 2)가 바로 그 예다)
이렇게 모든 열에 부어야 하는 물의 양을 처리해줬다면 이제 구멍이 났을 때를 처리해줘야 한다.
이 부분은 구현하기 쉽다. (a, b), (c, b)가 주어졌다면 일단 a열은 무조건 물의 양이 0이 된다. (water[a] = b)
이 때 없애는 기준이 되는 값을 h라 하자. 초기값은 b가 된다. (h = b)
그럼 이제 양쪽으로 값을 반영해 나가면 되는데 초기 물 양 - h >= 0일 때만 h를 빼줘야 한다.
0보다 작다면 그 위치는 값이 0이 되고 h는 그 위치의 초기 물 양과 같아진다. 즉, 기준이 바뀌게 된다.
물론 구멍이 여러 케이스가 존재하므로 한 열에서 빠지는 케이스가 여러 번 나올 수 있는데 남은 양의 최솟값을 취하면 되겠다.
머리 아파~
BOJ 4574: 스도미노쿠
Link : https://www.acmicpc.net/problem/4574
solution
문제에 그림이 들어갔는데 그 그림이 컬러면서 설명이 좀 긴거같으면 구현 문제 특 일단 머리가 아프다.
이 문제는 BOJ 2580: 스도쿠에서 한 단계 더 나아간 버전이다.
이전에는 1x1 칸씩 가로, 세로, 블럭을 체크하고 값을 갱신했다면 이번엔 1x2 또는 2x1을 갱신해야 한다.
고려해야 할 부분이 한 가지 더 있다. 같은 도미노는 사용할 수 없다는 점이다. (코드에서는 domino로 중복 체크)
문제에 설명돼 있듯이 도미노는 회전해서 사용할 수도 있다. AxB나 BxA나 같은걸로 취급한다는 말이다.
또한 같은 수도 사용할 수 없다. (AxA)
스도쿠 문제가 그렇듯이 가능한 경우의 수를 돌아보면서 안되는 케이스를 커팅해주면 된다. 따라서 DFS로 처리했다.
BOJ 3085: 사탕 게임
Link : https://www.acmicpc.net/problem/3085
solution
각 사탕에 대해서 인접한 사탕과 바꿔보고 가로, 세로로 각각 같은 색으로 연속된 개수들의 최댓값을 얻어야 한다.
좀 옛날 사람(..)이라면 애니팡 게임이랑 똑같다는걸 알 수 있다.
여기에 있는 문제들은 하루에 1문제씩 풀자고 계획했는데 첫 시작이 10월 11일이었으니 1달도 넘게 풀었다(..)
나름 기록하는 재미도 있고 경험치도 쌓이는 느낌이 있어서 의미있는거 같다!
코드 플러스에 있는 강의 문제들을 다 풀어보자!라는 생각으로 시작했는데 생각한 것보다 강의가 많기도 하고
문제 풀이도 (정말 하루에 이것만 풀면 괜찮겠지만?) 하루 1문제는 무리일거 같다. 난이도가 아주 멋져진다.
진지하게 대회를 준비할 생각이 있다면 가리지 않고 다 부딪혀 봐야겠지만 아직은 그런 생각이 크지 않아서
초기에 결심했던 목표들부터 달성하는걸 우선으로 해야겠다. 😀
댓글남기기