[BOJ] 12월 2주차
BOJ 16637: 괄호 추가하기
Link : https://www.acmicpc.net/problem/16637
solution
식의 길이가 짧기 때문에 브루트 포스로 풀 수 있다.
연산자 간에 우선순위가 없다! 다만 괄호가 있을 수 있어서 이 부분만 주의해서 처리해주면 된다.
괄호 안에는 숫자, 연산자를 포함해 3개만 들어가므로 3개중 첫 부분에만 표시했다. (sel[i] = true)
cal()은 연산자에 괄호 처리가 모두 완료됐을 때 계산하는 함수이고 DFS는 괄호를 추가하는 함수이다.
괄호에 묶인걸 1개의 집합이라고 할 때 식의 길이가 N이면 집합은 최대 (N-1)/2까지 생성될 수 있다.
다만 이 집합들은 서로 이웃할 수 없다. (이웃할 경우 숫자 하나를 공유하므로 이웃하면 안된다)
따라서 집합을 모두 넘버링했을 때 이전에 선택된게 prev번이라면 prev+2부터 선택될 수 있는 후보가 된다.
DFS에서는 집합의 수가 all개가 될 때까지 sel[i]에 표시하도록 했다.
BOJ 16638: 괄호 추가하기 2
Link : https://www.acmicpc.net/problem/16637
solution
위에서 푼 BOJ 16637: 괄호 추가하기에서 연산자 우선순위가 추가된 버전이다.
뭐 추가돼봤자 얼마나 더 복잡해지려니 했는데.. 생각한 것보다 케이스 분류를 꽤나 해야했고
초기값, 구조 등을 잘못 설정해서 시간을 엄청 잡아먹었다. 거의 다 푼거 같은데 틀리는건 억울해서 계속 제출해서 맞았다.
일단 괄호가 곱하기보다 우선 순위에 있기 때문에 괄호로 둘러싸인 부분을 먼저 고려해주어야 한다.
그 다음은 곱하기를 고려해야 하는데, 곱하기가 오는 경우 계속 곱해야 할지도 몰라 priority()로 구현했다.
근데 괄호와 곱하기가 섞인 다음과 같은 예에서 고려해줄 부분이 좀 더 생기게 된다.
$A+(B+0)\times C (A, B, C\geq 0)$
그리고 위 코드 기준이지만 곱하는 경우 priority()로 들어가서 식의 일부를 먼저 계산하게 되는데
cal()로 돌아왔을 때 식의 인덱스를 올바르게 표시해주기 위해 priority()는 2가지 값을 반환해주도록 설정했다.
첫 번째는 계산값을, 두 번째는 인덱스를 몇 칸 건너뛰어야 하는지를 의미한다.
곱하기와 괄호가 연쇄적으로 있는 경우 두 번째 값이 커질 수 있으므로 주의해야 한다.
BOJ 2982: 국왕의 방문
Link : https://www.acmicpc.net/problem/2982
solution
국왕이 지나간 길을 사용한 시간을 따로 적어준 후 현재 시각과 비교해 시간을 추가할지 여부를 고려해주면 된다.
처음보는 컨셉이어서 쇼킹했는데 TC만 충분히 분석해도 답을 낼 수 있었다.
BOJ 16922: 로마 숫자 만들기
BOJ 2780: 비밀번호
Link : https://www.acmicpc.net/problem/2780
solution
각 숫자들로부터 인접한 숫자들로 나아가면서 길이가 N일 때 1을 반환하도록 재귀를 돌려준다.
메모이제이션해서 풀어주면 된다.
BOJ 2621: 카드게임
BOJ 18223: 민준이와 마산 그리고 건우
Link : https://www.acmicpc.net/problem/18223
solution
건우가 있는 지점을 거치지 않는 V번으로의 최단 거리를 다익스트라를 통해 갱신한 후 띠로 저장해두고
1 -> P -> V로 2번 다익스트라를 써서 갱신한 후 비교해서 답을 출력하면 된다.
BOJ 14461: 소가 길을 건너간 이유 7
Link : https://www.acmicpc.net/problem/14461
solution
각 위치에서 용량이 t인 간선을 상하좌우로 연결해준다.
일반적으로 다익스트라의 결과가 반영되는 dist는 dist[도착점]으로 1차원 배열로 나타냈는데
이 문제에서는 길을 3번 건널 때마다 풀을 먹는 시간을 추가해야 하므로 dist를 2차원 배열로 설정했다.
첫 번째 칸은 똑같이 도착점을, 두 번째 칸은 풀을 안먹고 갈 수 있는 횟수(remain)를 의미한다.
우선순위 큐의 top의 remain은 매번 달라질 수 있으므로 구조체를 이용해 따로 설정해줬고
시작점은 remain을 카운트하지 않지만 도착점에서는 remain을 카운트해야 하므로
모든 remain에 대해서 도착점에서의 dist값 중 최솟값을 출력하도록 했다.
확실히 다익스트라 유형 문제가 골드3 이상을 넘어가면서 머리를 써야하는 문제가 등장하는 것 같다.
BOJ 16234: 인구 이동
Link : https://www.acmicpc.net/problem/16234
solution
구현 문제.
영역 바운더리를 찾는건 DFS로 처리했다.
어차피 인접한 위치(상하좌우)를 각 위치에서 조사하면서 두 영역간의 차이값이 [L, R]에 들어오는지 여부만
확인해주면 되므로 벽에 해당하는 내용을 별도로 선언해줄 필요가 없었다.
모든 위치에서 영역을 탐색하도록 시도하는데 영역의 범위가 1이라는건 아무 곳으로도 이동할 수가 없다는 말이므로
이동할 수 있는 케이스 즉, 영역의 범위가 2 이상일 때 답을 갱신했다.
BOJ 5427: 불
Link : https://www.acmicpc.net/problem/5427
solution
BOJ 4179: 불!과 같은 BFS 문제.
설명 중 다음 내용을 주의해서 구현해야 한다.
불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다.
BOJ 1669: 멍멍이 쓰다듬기
BOJ 4620: Pascal's Travels
Link : https://www.acmicpc.net/problem/4620
solution
간단한 DP 문제. 바닥에 써진 만큼 남/동쪽으로 이동할 수 있다.
도착점에 도달하면 1을 반환하도록 재귀를 돌려주되 메모이제이션해서 답을 구하자.
BOJ 16925: 문자열 추측
Link : https://www.acmicpc.net/problem/16925
solution
입력으로 들어오는 문자열이 일단 접두사인지 접미사인지 모르므로 하나하나 시도해봐야 한다.
단, 같은 길이의 문자열은 2개만 들어오므로 문자열 길이를 기준으로 정렬해서 쌍으로 처리했다.
채워지지 않은 문자가 있다면 채워주고, 만약 일치하지 않는 문자가 있다면 다음 케이스로 이동하도록 했다.
하나하나 케이스별로 시도해본다는 점에서 브루트 포스 유형으로 분류할 수 있겠다.
BOJ 10251: 운전 면허 시험
Link : https://www.acmicpc.net/problem/10251
solution
DP 문젠데 평소에 풀던 문제와는 조금 달라서 놀랐다.
평소에 풀던 DP 문제는 문제에서 요구하는 값을 바로 구할 수 있었는데 이 문제는 한 단계를 더 거쳐야 한다.
무슨 말이냐면 이 문제에서 요구하는 답은 조건을 만족하면서 목적지에 도달하는 최단 시간을 구해야 하는데
DP로 최단 시간을 바로 구하는게 아니고 최소 연료량을 구한 후 G보다 작거나 같은 모든 최소 연료량에 대해서
최단 시간을 구해야 한다. 이렇게 할 수 있는 이유가 각 도로를 거치는데 드는 시간 고정 + 총 이동 거리가 고정이어서 그런 것 같다.
아마 두 가지 중에 하나라도 고정이 되지 않는다면 인자로 놓아야 한다.
근데 연료량이 인자로 들어오면 메모리가 터져서 안될 것 같은데.. 풀 수 있는 방법이 또 있는지 모르겠다.
dp[x][y][k][d] : 현재 위치가 (x, y)고 회전한 횟수가 k, 방향이 d(동, 서)일 때 든 최소 연료량
도착점이 (n-1, m-1)로 고정돼 있으므로(0-based) dp[n-1][m-1][k][d]에서 g보다 큰 경우는 모두 가지치기 해주고
위에서 언급한 것처럼 모든 후보에 대해서 최단 시간을 구해주면 된다.
BOJ 1800: 인터넷 설치
Link : https://www.acmicpc.net/problem/1800
solution
다익스트라 문제다.
요구하는 조건이 조금 특이하다. N번까지 도달하는 경로 중 K+1번째로 비싼 비용의 최솟값을 구해야 한다.
비용을 K번 무시할 수 있다는 특징때문에 dist를 다음과 같이 정의했다.
dist[i][k] : i번까지 도달하는데 드는 비용을 k번 무시했을 때 최대 비용
remain 변수는 말그대로 무시할 수 있는 잔여 횟수를 의미한다.
다익스트라의 성격을 그대로 가져가는데, 함수에 다음 부분을 추가해야 한다.
if (remain > 0 && dist[next.first][remain-1] > distance) {
dist[next.first][remain - 1] = distance;
pq.push({ next.first, distance, remain - 1 });
}
BOJ 10216: Count Circle Groups
Link : https://www.acmicpc.net/problem/10216
solution
Union-Find 알고리즘으로 풀었다.
제목이 Circle Groups니까 서로 닿거나 겹치는지 여부는 점과 점 사이의 거리와 두 반지름을 더한걸 가지고 비교하면 되고
1부터 N까지 돌면서 스스로가 집합의 번호와 같은 것(부모)의 개수를 출력하면 된다.
BOJ 16937: 두 스티커
Link : https://www.acmicpc.net/problem/16937
solution
브루트 포스 문제.
처음에도 그렇고 풀고나서도 그렇고 이 문제가 실버 5인게 놀라웠다.
처음에 문제 설명만 대강 읽고 달려들었는데 스티커를 2개만 붙여도 된다는 사실을 뒤늦게 알고나서 허무함을 느꼈지만
그렇다고 하더라도 스티커를 90도 회전할 수 있다는 점, 두 스티커를 서로 반대쪽 대각선에 붙이는게 더 빠르다는 점
이 2가지를 갖추지 못했다면 풀기 어려웠을걸로 생각된다. (처음에 후자를 고려하지 않아 TLE를 받았다)
범위가 크지 않아서 처음에 붙이는 스티커를 (0, 0)에 고정해놓고 붙여지는 영역을 모두 visited에 표시했는데
사실 이 방법은 굉장히(!!) 비효율적이다. 첫 스티커의 시작점, 두 번째 스티커의 시작점이 고정돼 있어서
어떻게 수식으로 서로 겹치지 않도록 수식으로 처리할 수 있겠지만 귀찮아서 일일이 때려박았다.
처음에 여러 스티커를 한 번에 붙여야 하는 줄 알고 함수를 만들어서 재귀를 돌릴 생각이었는데
2장만 붙여도 되니 굳이 함수로 구현할 필요는 없어보인다. 코드만 좀 복잡해졌다.
BOJ 1633: 최고의 팀 만들기
Link : https://www.acmicpc.net/problem/1633
solution
DP 문제.
팀을 안고르거나, 흑팀을 고르거나, 백팀을 고르는 경우 3가지를 메모이제이션해서 답을 구해주자.
BOJ 3933: 라그랑주의 네 제곱수 정리
Link : https://www.acmicpc.net/problem/3933
solution
DP 또는 브루트 포스로 풀 수 있다. 위 코드는 DP 풀이.
dp[i][j][k] : 더해온 제곱수 중 최댓값이 j일 때 j보다 작거나 같은 값을 제곱해 최대 k번 더했을 때 i가 되는 횟수
DP가 원래 그렇지만 값과 값 사이의 관계를 잘 떠올린다면 이 문제의 경우 점화식은 쉽게 찾을 수 있다.
BOJ 2398: 3인통화
Link : https://www.acmicpc.net/problem/2398
solution
마지막으로 입력받는 위치인 세 곳을 s1, s2, s3이라 하면
s1, s2, s3에서 다익스트라를 돌리고 모든 점에 데해서 세 곳에서의 최단 거리 합이 최소인 지점을 찾는다.
그럼 그 지점으로부터 각 시작 지점으로 경로를 역추적하면 된다.
BOJ 2840: 행운의 바퀴
Link : https://www.acmicpc.net/problem/2840
solution
놓치기 쉬운 예외가 존재하는 구현 문제. 나는 구현 문제가 싫다
처음에 빈 칸은 모두 ‘?’을 채우고 시작하는데 나중에 중복되는 문자가 있는지 체크할 때 ‘?’는 예외 처리 해줘야한다.
또, 돌렸는데 이미 문자가 등록된 칸인 경우 입력받은 문자와 같을 수 있다.
BOJ 1043: 거짓말
Link : https://www.acmicpc.net/problem/1043
solution
Union-Find 알고리즘으로 풀었다.
진실을 아는 집합을 사전에 만들어놓고 입력받는 사람들을 묶어놓는다.
이후 M개의 집합에 대해 속한 사람들을 서로 같은 집합으로 묶는다.
만약 그 사람들 중 진실을 아는 사람이 단 한 명만 있더라도 진실을 아는 집합으로 묶이게 된다.
때문에 순차적으로 집합을 탐색하면서 진실을 아는 집합에 속해있는지 여부를 확인하면 된다.
모두 진실을 아는 집합에 속해있지 않은 사람들로 구성된 집합이라면 답을 갱신해주면 되겠다.
BOJ 16938: 캠프 준비
Link : https://www.acmicpc.net/problem/16938
solution
브루트 포스 문제.
조건에 맞는 경우의 수를 세야하는 문젠데 딱히 커팅이 필요하지도 않아서 어렵지 않다.
설명에 충실하게 기저 사례를 처리하고 나머지는 재귀를 돌려주자.
BOJ 12026: BOJ 거리
Link : https://www.acmicpc.net/problem/12026
solution
DP 문제.
현재 위치 다음에 있는 문자들 중에 다음으로 와야 할 문자가 있는지 탐색하면서 진행한다.
시간 복잡도는 $O(n^2)$
BOJ 1577: 도로의 개수
Link : https://www.acmicpc.net/problem/1577
solution
DP 문제.
메모리 상한이 16MB밖에 안된다는게 이 문제의 특징인 것 같다. 처음에 이 부분을 간과해서 틀렸다.
막힌 도로의 길이가 항상 1인점 + 도착점까지 무조건 최단 거리로 가야 한다는 점 때문에
막힌 도로의 정보를 좌표와 방향만으로 표시할 수 있다. (ban[x][y][dir])
이외 로직은 일반적인 DP문제와 같다.
BOJ 11781: 퇴근 시간
Link : https://www.acmicpc.net/problem/11781
solution
최근 들어서 많이 제출하고 겨우 맞은 문제는 이게 처음이다. 어떻게 9번이나 틀렸을까.
다익스트라로 풀어야 하고, 퇴근 시간의 시작과 끝 그리고 도로의 길이의 상한이 10억이므로
오버플로우를 피하기 위해 long long을 사용해줘야 한다. 당연히 초기화 값도 충분히 커야한다.
부동소수점 오차도 고려해줘야 하고.. 결정적으로 다익스트라 함수 내의 조건문을 잘 정해줘야 한다.
당연한거 아닌가? 싶을텐데 당연한건 맞지만(..) 고려해줘야 하는 케이스가 좀 돼서 머리가 조금 아프다.
현재 시각이 퇴근 시간보다 앞에 있는지, 속해 있는지 그리고 퇴근 시간이 지난 뒤인지 크게 3가지로 나눠야 하고
또 각각 케이스에서 도로의 길이가 얼마나 짧은지, 긴지를 모르기 때문에 또 케이스를 나눠줘야 한다.
BOJ 2174: 로봇 시뮬레이션
Link : https://www.acmicpc.net/problem/2174
solution
제목 그대로 구현 문제다. 난이도가 높진 않은데 습관때문에 좀 틀릴 수도 있는 함정이 있다.
- 맵의 가로, 세로 그리고 좌표 x, y에 대한 입력 설명을 잘 읽자. x는 세로가 아니다.
- 문제 설명에 다음과 같은 문구가 있다. 방향 설정에 꼭! 주의하자.
x좌표는 왼쪽부터, y좌표는 아래쪽부터 순서가 매겨진다.
BOJ 16943: 숫자 재배치
Link : https://www.acmicpc.net/problem/16943
solution
a를 string으로 입력받고 순열을 돌리면서 b보다 작거나 같은 수 중 최댓값을 취한다.
BOJ 17090: 미로 탈출하기
Link : https://www.acmicpc.net/problem/17090
solution
DP로 풀었다.
맵에 방향값을 표시해주고 맵 밖으로 나가는 경우를 1로, 아니면 0으로 처리될 수 있도록 설정해주자.
BOJ 11952: 좀비
Link : https://www.acmicpc.net/problem/11952
solution
BFS + 다익스트라 문제.
감염된 도시에서 위험한 도시를 찾아내기 위해 BFS로 처리해주는데, 몇 번이나 더 나아갈 수 있는지를 기록해줘야 한다.
이렇게 기록된 값은 다음 큐에서 남은 횟수와 비교해서 더 이상 처리할 수 없을 경우 제외해줘야 시간/메모리 측면에서
효율적으로 처리할 수 있기 때문이다.
위 코드에서는 이 부분에 해당한다. if (cnt < 0 || warn[cur] >= cnt) continue;
숙박비의 상한이 크므로 int말고 long long을 쓰자.
BOJ 2960: 에라토스테네스의 체
BOJ 16945: 매직 스퀘어로 변경하기
BOJ 3114: 사과와 바나나
Link : https://www.acmicpc.net/problem/3114
solution
DP 문제.
경계선을 기준으로 위 아래에서 각각 원하는 값만 취해와야 한다. 가령, 아래는 A값을, 위에는 B값을 가져와야 한다.
일일이 구한다면 당연히 시간 초과를 피할 수 없다. 하지만 각 위치에 있는 값은 정해져 있으므로 누적합으로 처리하면 편리하다.
위 코드에서 a와 pSum은 각 인덱스가 행/열/A, B를 의미하고 a는 각 위치에 있는 값을, pSum은 누적합을 나타낸다.
이동하는 방향은 총 3가지다.
처음엔 오른쪽, 오른쪽 대각선으로 이동할 때만 값을 더해주면 되겠다고 생각했는데 TC도 통과하질 못했다.
왜 그런가 하니 아래로 이동할 경우 아무 값도 더해주질 않으면 위아래로 이어지는 경계선을 제외한 값들을
온전히 얻을 수 없다. 열이 증가하는 방향일 때만 갱신되므로 경계선을 포함하는 위치의 값도 더해주게 된다.
그래서 (x-1, y) -> (x, y)로 왔을 경우 prev를 1로, 아니면 0으로 처리하도록 인자를 추가했고,
아래로 이동할 경우 위에 있는 값(pSum[x-1][y][1])을 더하도록 해줬다.
또, 아래로 이동해 온 경우(prev = 1) 그리고 열이 증가하는 방향으로 움직일 때 아래 있는 값(pSum[x+1][y][0])을
더하도록 처리해줬다. 그래야 경계선을 제외한 같은 열의 원소들을 깔끔하게 처리할 수 있게 된다.
어떻게 처리해야할지는 금방 떠올릴 수 있었는데 반례를 빠르게 처리하지 못해서
그리고 삼항 연산자로 값을 더하는 부분 때문에 (문법 문제로 보이지만) 시간을 많이 잡아먹었다. 안타깝다.
BOJ 5972: 택배 배송
BOJ 2176: 합리적인 이동경로
Link : https://www.acmicpc.net/problem/2176
solution
다익스트라 + DP 문제.
합리적인 이동경로가 뭔지 모르겠다면 이 글을 참고하자.
2번 정점이 도착점으로 고정돼 있으므로 2번에서 다익스트라를 돌려주자.
그럼 모든 점으로의 최단 거리를 구할 수 있는데, 1번 시작점으로부터 도착점까지 가는 경로 중
합리적인 이동경로에 해당되는 케이스에 대해서만 재귀를 돌려주자. 메모이제이션해서 답을 구하면 끝이다.
BOJ 16562: 친구비
Link : https://www.acmicpc.net/problem/16562
solution
Union-Find 문제.
- 서로 친구인 학생들을 집합으로 묶어준다.
- 집합별로 최소 비용을 cost[i]에 기록한다.
- 집합별 비용을 sum에 모두 더해주고, k보다 크면 Oh no를, 아니면 sum을 출력한다.
BOJ 16946: 벽 부수고 이동하기 4
Link : https://www.acmicpc.net/problem/16946
solution
Union-Find 문제.
모든 빈 칸들을 인접한 빈 칸들과 같은 집합으로 묶어주고, 집합별 원소의 개수를 구한다.
그럼 벽이 있는 칸들에 대해서 현재 위치를 포함한 인접한 빈 칸들의 집합별 원소의 개수를 카운트 해준다.
단, 인접한 빈 칸들이 서로 같은 집합일 수 있다. 이 경우 한 번만 카운트 되도록 처리해준다.
각각 이동할 수 있는 칸을 무조건 10으로 나눈 나머지로 출력해야 한다. (문제 설명 참고)
댓글남기기