[BOJ] 2월 문제풀이
BOJ 11576: Base Conversion
BOJ 17103: 골드바흐 파티션
Link : https://www.acmicpc.net/problem/17103
solution
$10^6$까지 소수 여부를 전처리한 후(에라토스테네스의 체)
a의 중간까지 매 케이스마다 탐색해서 값을 찾아주면 된다.
BOJ 1309: 동물원
Link : https://www.acmicpc.net/problem/1309
solution
DP 문제.
0층부터 시작해서 조건에 맞춰 채워가면서 n-1층에 도착하면 1을 반환하도록 설정했다. (0-based)
열은 2개뿐이므로 당연히 열 모두 채울 수는 없으며 사자를 1마리 배치하거나 또는 배치하지 않는 경우 2가지만 고려하자.
인자에서 cur을 현재 층, col을 사자가 들어있는 열의 정보라고 하자.
현재 층에 만약 사자가 존재한다면 다음 층에는 같은 열에 사자가 오지 않도록 하면 된다.
위의 경우를 제외한 모든 케이스를 세주자. 또 항상 9901로 나눈 나머지를 구해야 함에 주의하자.
BOJ 1057: 토너먼트
Link : https://www.acmicpc.net/problem/1057
solution
브루트포스 문제.
라운드를 거칠 때마다 우승자의 번호가 규칙적으로 바뀌는 점에 유의하면 쉽게 풀 수 있다.
BOJ 1248: 맞춰봐
Link : https://www.acmicpc.net/problem/1248
solution
백트래킹 문제.
모든 케이스를 돌면서 모든 조건을 탐색하면 $21^{n} /times n(n+1)/2$이 걸리므로 TLE를 받는다.
때문에 이 문제의 난이도가 개인적인 생각으로는 백트래킹치고 높은데, 가지치기를 하는게 포인트다.
4달 전에 TLE를 받고 포기했다가 코드 플러스에 실려있어서 다시 풀어보게 됐다.
다시 구현을 해보고 N=9인 케이스를 넣었는데 4초를 넘어가서 왜 그런가 체크해보니
처음에 값 할당을 모두한 후, 재귀를 돌리며 조건에 맞는지를 탐색하는 방식으로는 시간이 많이 걸리는듯 했다.
아무래도 재귀를 많이 호출하는 부분에서도 시간이 좀 걸리는 모양이었다. (크진 않겠지만)
딱 말하면 틀린 답을 가지고 너무 많은 조건을 탐색해본다는 점인데, 이 부분을 개선하는게 관건이었다.
결론적으로 다 갈아엎고 값 할당을 하나씩 하면서 조건을 탐색하기로 했다.
이렇게 하니 이전엔 모든 값을 가지고 많은 조건을 탐색해봤는데 이번엔 필요한 만큼만 탐색을 하게 됐고
제출해보니 시원하게 100ms로 AC를 받을 수 있었다.
BOJ 14391: 종이 조각
Link : https://www.acmicpc.net/problem/14391
solution
브루트 포스 - 비트마스크 문제.
모든 자리를 비트마스킹으로 처리하는게 포인트다.
N의 상한이 4이므로 최대 16자리까지 컨트롤 해야하는데 $2^{16}$이라 해야봐야 $65536$밖에 안되므로
배열의 크기로 사용하는데 무리가 없다.
남은건 구현인데 개인적으로 디버깅을 하는데 시간이 좀 걸렸다.
전체 사이즈가 NxM이므로 탐색해야 하는 상한이라던가 자리 등은 적당히 조작해서 매칭하면 되고
잘 짰다면 문제가 아마도 없었을텐데 나같은 경우 이미 체크된 자리라면 다음으로 넘어가는 코드
if (chk & (1 << cur)) {}에서 재귀를 돌리고 밖으로 넘어가지 못하도록 continue 또는 return 처리를
해주질 않아 조금 헤맸었다.
브루트 포스답게 각 위치에서 제자리만 택하거나 가로, 세로 확장하는 케이스를 모두 처리해주면 되겠다.
비트마스킹 문제를 풀어본 경험이 없다면 절대로 못풀었을 것 같다.
BOJ 2146: 다리 만들기
Link : https://www.acmicpc.net/problem/2146
solution
DFS로 육지인 부분을 돌면서 섬마다 넘버링을 해준 후($O(n^2)$)
위치 두 곳을 $(x_1, y_1), (x_2, y_2)$라 하면 최단 거리는 $|x_1-x_2|+|y_1-y_2|-1$이므로
모든 쌍이 되는 섬들에 대해 조사해보면 된다.
BOJ 2250: 트리의 높이와 너비
Link : https://www.acmicpc.net/problem/2250
solution
어떤 방법으로 풀어야 좋을지 한바퀴정도 헤메다가
아이디어가 떠올라서 구현해보니 코드량도 엄청 적게 수월하게 구현했다.
다만 루트 노드를 설정하는 과정에서 당연히 1번이라 생각하고 제출했다가 WA를 받았는데
이 문제는 루트 노드가 뭔지 알려주지 않았으므로 찾아야 한다.
리프 노드에서 부모로 끝까지 역추적해서 루트 노드를 구해주면 된다.
각 노드의 x축 번호를 어떻게 할당하는지 곰곰이 생각해보면 의외로 답이 쉽게 나온다.
- 왼쪽 자식이 있다면 리프 노드를 찾을 때까지 계속 진입한다. 리프 노드에서 넘버링한다.
- 부모 노드로 돌아왔을 때 넘버링한다.
- 오른쪽 자식이 있다면 1번으로 돌아간다. 없다면 2번으로 돌아간다.
BOJ 16954: 움직이는 미로 탈출
Link : https://www.acmicpc.net/problem/16954
solution
BFS 문제.
일반적인 길찾기 컨셉에서 벽이 1초에 1칸씩 아래로 내려간다는 점이 추가된 버전이다.
예전에 풀다가 어떻게 예외 처리를 잘못했는지 계속 특정 케이스를 못넘어가서 포기했었다.
이번에 알고리즘 중급 1/3 - BFS (연습)에 실려있어서 다시 도전해봤는데
생각보다 되게 쉽게 풀었다. 복잡하게 생각할 필요가 없었던 문제였다.
가장 먼저 체크해야할 점은 맵의 크기가 8x8로 고정이다.
input으로 들어오는 초기 맵 상태에 있는 벽이 어디에 있든 8칸이 지나면 다 빈 칸이 된다.
1초에 1번 9가지 방법으로 이동한 후 벽이 내려오는걸 직접 구현하지 않고 캐릭터를 한 칸 위로 이동하자.
그럼 거쳐가는 위치(nx, ny)도 벽이 아니어야 하고, 도착 지점(nx-1, ny)도 벽이 아니어야 한다.
정해진 맵에서 벽은 이동하지 않고 캐릭터를 역으로 위로 올리기로 했기 때문에,
캐릭터의 위치(x, y)가 x<=0이면 사실상 도착 지점으로 이동할 수 있음을 알 수 있다.
(실제로 맨 아랫줄이 사라지면 맨 윗줄은 벽이없는 빈 칸으로 새롭게 추가된다)
때문에 위의 경우 1을 출력하고 종료, 그렇지 않으면 최종적으로 0을 출력해주면 되겠다.
BOJ 16933: 벽 부수고 이동하기 3
Link : https://www.acmicpc.net/problem/16933
solution
BFS 문제.
BOJ 14442: 벽 부수고 이동하기 2에서 한 단계 더 나아간 버전이다.
벽을 부술 수 있는 횟수가 정해져 있고, 낮에만 벽을 부술 수 있다고 쓰여 있다.
chk[x][y]는 현재 위치가 (x, y)이고 지금까지 벽을 부순 횟수를 의미한다.
제자리에 있을 수 있는 케이스가 뭔지 잘 생각해야 하는데,
- 벽을 부수지 않은 상태
- 밤 시간 복잡도 때문에 다음 2가지 조건을 만족해야 제자리에 있을 수 있도록 해야한다.
BOJ 2644: 촌수계산
Link : https://www.acmicpc.net/problem/2644
solution
BFS 기본 문제.
인접 행렬로 만들어준 뒤 중복을 체크해가면서 답을 카운팅해주면 된다.
BOJ 1080: 행렬
Link : https://www.acmicpc.net/problem/1080
solution
그리디 문제.
입력받은 행렬을 a, b라고 하면, 탐색하면서 a[i][j]와 b[i][j]가 같은지 여부를 확인한다.
다르다면 무조건 바꿔야 하는 상태이므로 해당 위치를 33의 좌측 상단이라고 생각하고
33 행렬을 한꺼면에 뒤집어준다. 그렇지 않으면 그냥 넘어가도록 한다.
여태까지 바꿔온 내용들이 다음 순서에서 영향을 받지 않도록 범위에 유의.
BOJ 2138: 전구와 스위치
Link : https://www.acmicpc.net/problem/2138
solution
그리디 문제.
현재 위치(인덱스)를 i라 하면 직전 위치인 i-1에서 a와 b가 다를 때 무조건 바꾸는 연산을 해줘야 한다.
그렇지 않으면 다음 위치로 넘어가면서 절대로 바꿀 수 없게 되기 때문이다.
첫 번째 인덱스(a[0])에서는 a[-1]이 존재하지 않기때문에 바꾸는 연산을 적용할지 말지 모두 시도해봐야 한다.
BOJ 19584: 난개발
Link : https://www.acmicpc.net/problem/19584
solution
스위핑 문제.
어떤 정점을 지났을 때 해당 정점과 연결된 모든 엣지에 대한 가중치를 취할 수 있는 점에 주목해야 한다.
때문에 엣지의 양 끝 점들의 y값을 기준으로 점들을 정렬한 후 스위핑하면서
해당 점이 시작점인지 여부에 따라 값을 갱신하고 이 때 최댓값을 취해주면 된다.
BOJ 16357: Circuits
Link : https://www.acmicpc.net/problem/16357
solution
스위핑 + Lazy Propagation 문제.
여기서 Lazy Propagation의 쿼리는 구간합이 아닌 구간 최댓값을 구하도록 해주어야 한다.
점들을 정렬하고 스위핑을 하는데 기준이 되는 두 점을 정해야 하므로 매 순간 한 점을 지정한다고 하자.
그렇다면 해당 점의 y좌표와 만나는 모든 사각형을 제외한 나머지 중 모든 y값에 대해 최댓값이 되는 점을
Lazy Propagation으로 쿼리를 이용해 처리하면 된다.
근데 문제가 있다. 만약 큰 사각형이 작은 사각형을 아예 감싼다고 하자.
그리고 위의 두 사각형을 지나는 선과 겹치지 않는 다른 영역에 대해 선이 지나가야 최댓값이 나온다고 하자.
그럼 큰 사각형의 시작선을 만나고 바로 [시작, 끝]에 대해 -1을 업데이트하고 쿼리로 값을 가져온다면
나중에 작은 사각형을 없앨 차례가 왔을 때 직전에 처리한 큰 사각형의 정보를 잃어버리게 된다.
(무슨 바보같은 삽질을 한거냐고 할 수도 있겠지만 어떻게 개선해야할지 모르겠어서 정말 헤맸다)
결론적으로는 스위핑하는 for문 밖에 카운팅해주는 변수를 따로 선언해놓고
해당 변수를 선의 정보를 갖고 관리해주면서 최댓값을 취하도록 하니 해결할 수 있었다.
5개월만에 다시 손대게 되면서 또 다시 좌절을 겪고 푸는데까지 적지 않은 시간을 소비했다.
은근 간단한것 같으면서도 상당히 어렵다고 느껴지는 테마라고 생각한다😓
BOJ 1963: 소수 경로
Link : https://www.acmicpc.net/problem/1963
solution
에라토스테네스의 체 + BFS 문제.
각 자릿수를 0~9로 돌려주면서 소수인 수에 대해 카운팅을 하며 넘겨주자.
항상 4자릿수가 되어야 함에 유의.
BOJ 1963: 트리
Link : https://www.acmicpc.net/problem/1963
solution
간단한 그래프 문제.
구현하는데 크게 어렵진 않으나 루트 노드가 항상 0번이 아님에 유의.
BOJ 1963: 트리
Link : https://www.acmicpc.net/problem/1963
solution
간단한 그래프 문제.
구현하는데 크게 어렵진 않으나 루트 노드가 항상 0번이 아님에 유의.
BOJ 2636: 치즈
Link : https://www.acmicpc.net/problem/2636
solution
BFS 문제.
다른 부분은 그렇다치고 가장자리를 체크하는게 포인트다.
쉽게 구현할 수 있을줄 알았는데 시간이 꽤 걸렸다.
어느 케이스에서 걸리는지 모르겠는데 deque로 0일때 우선으로 처리하는게 안돼서
시간을 더 쓰는 방법을 택했는데 최대 100x100이어서 통과하는데 무리는 없었다.
BOJ 2638: 치즈
BOJ 2109: 순회강연
Link : https://www.acmicpc.net/problem/2109
solution
그리디 문제.
나중에 할 수 있는 케이스들이 그렇지 않은 케이스보다 가격이 높은 경우 주의해야한다.
좀 더 자세히 말하면 위와같은 케이스가 많아서 기간이 짧고 강연료가 적은 케이스를 택하지 못하는 경우가
생길 수 있다는 말이다. 예시는 여기에 있다.
BOJ 18407: 가로 블록 쌓기
Link : https://www.acmicpc.net/problem/18407
solution
Lazy Propagation을 이용한 Segment Tree 문제.
블럭이 쌓이면서 일부분이 허공에 놓이게 돼도 그렇지 않은 부분과 높이가 같아지게 되므로
구간 [a, b]에서 최댓값을 h라 하면 [a, b]의 모든 값을 h+1로 수정하면 된다.
BOJ 1744: 수 묶기
Link : https://www.acmicpc.net/problem/1744
solution
그리디 문제.
음수는 제일 작은 값끼리, 양수는 제일 큰 값끼리 묶어주자.
이 때 0은 음수와 무조건 묶고, 양수와는 묶지 않아야 한다.
1은 대상이 음수, 0, 양수 중 어떤 케이스든 간에 묶지 않아야 한다.
즉, 0과 1에 대한 예외 처리가 필수.
BOJ 11559: 수 묶기
Link : https://www.acmicpc.net/problem/11559
solution
구현 문제.
맵의 가로, 세로 길이가 고정돼 있고 크기도 꽤 작으므로 굳이 효율적인 방법을 떠올릴 필요는 없어 보였다.
BFS로 각 블럭마다 그룹으로 묶어버리고, 그룹에 소속된 블럭이 4개 이상이면 ‘.’으로 바꿔준다.
‘.’으로 바꾸는 연산을 했을 경우 BFS()에서 true를 리턴하도록 함으로써 탐색을 더 할지 말지를
결정하도록 한다.
BFS가 true라면 허공에 떠있는 블럭을 아래로 내려줘야 한다.
때문에 각 열에서 열마다 쌓인 블럭들의 최대 높이의 인덱스를 base[col]에 넣어준다.
만약 base[col]이 갱신됐다면 허공에 블럭이 있는지를 탐색하고 있다면 끌어내려주면 된다.
BFS()가 false를 반환할 때까지 위 과정을 반복한다.
BOJ 2662: 기업투자
Link : https://www.acmicpc.net/problem/2662
solution
DP 문제.
현재 기업의 번호를 cur, 남은 금액을 remain이라 하자.
그리고 f(cur, remain)을 cur번째 기업에서 remain의 금액이 있을 때 투자해서 얻는 최대 금액이라고 하자.
$inv \in [0, remain]$이고 profit[cur][money]를 cur번째 기업에서 moeny만큼 투자해서 얻는 이윤이면,
$f(cur, remain) = max(f(cur, remain), f(cur+1, remain-inv)+profit[cur][inv])$
가 성립한다.
예전에 풀었던 문제였지만 스터디하면서 다시 만나게 돼가지구 다시 풀게 됐다.
출력 내용을 자세히 읽질 않아서 최대값만 출력한다고 무턱대고 바로 짰는데 예제보니 더 해야할게 있더라.
덜렁대서 조건을 놓치는 경우가 없도록 주의해야겠다. 각 기업당 쓰는 투자 금액도 출력하는 부분때문에
난이도가 골4~5 에서 골3으로 올라간걸로 보인다.
댓글남기기