MathJax.Hub.Register.MessageHook("Math Processing Error",function (message) { alert("Math Processing Error: "+message[1]); }); MathJax.Hub.Register.MessageHook("TeX Jax - parse error",function (message) { alert("Math Processing Error: "+message[1]); });
16 Nov 2020

[BOJ] 11월 2주차

문제풀이

이번 주도 다른 주와 특별히 다르지 않은 집콕PS로 일상을 채웠다.
좀 나가보려 하면 확진자가 많고 약속도 못잡고 주절주절
다음 주차부터는 간만에 레벨업을 해서 플레1을 갈 것 같은데 다이아는 글쎄 갈 수 있을지 모르겠다.
가끔은 탄력받아서 만든 결과물에 취해 뿌듯함으로 마무리할 때도 있지만 벽을 느끼면서 한숨쉴 때가 다반사인거 같다.
그래도 지금 안하면 언제든 또 시간들여야 하는 영역인건 분명하니 할 수 있을 때 더 공들여보자!

BOJ 7570: 줄 세우기

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

solution

DP 문제다.
처음엔 왠지 익숙한 느낌이 들어서 전체 길이(n) - LIS가 정답인줄 알고 제출했다가 시원하게 WA를 받았다.
이게 왜 틀렸는지 증명을 못하겠어서 찾아보다가 딱 맞는 qna를 발견했다.
증가는 하되 연속된 값으로 증가를 해야한다는 말인데(2, 3, 4 처럼) 이 부분 역시 DP로 처리할 수 있다.
인풋이 들어올 때마다 처리해주면 되는데, 현재 값을 x라고 하자.
그럼 dp[x]는 x까지 연속된 숫자로 증가하는 수열의 길이라고 정의할 수 있다. 점화식이 굉장히 간단해진다.
\(dp[x] = dp[x-1] + 1\)
모든 dp[x]중 최댓값을 취해서 출력해주면 되겠다.

BOJ 2465: 줄 세우기

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

solution

? 놀랍게도 방금 전에 풀었던 문제 이름과 같다.
하지만 요구하는 내용은 완전히 다르다. 인풋이 무작위로 들어오고 요구하는 순서와 조건에 맞도록 출력해야 한다.
세그먼트 트리를 가지고 조금 응용한 문제다.

모든 키들은 상한이 \(2\times 10^9\)이므로 세그먼트 트리에서 인덱스에 때려넣기엔 값이 너무 크다.
근데 다행히도 N의 상한이 \(10^5\)다! 따라서 값들을 크기 순서에 맞춰서 압축해주고 같은 값은 같은 순위로 설정한다.
(기준이 크기순인 각 순위를 업데이트 해주는 이유는 앞에 작거나 같은 값의 갯수가 주어지기 때문)
(위 코드에서 convert[i]는 크기순으로 i번째에 있는 값을 의미한다)
이렇게 부여한 순위는 세그먼트 트리에 인덱스를 순위로 +1씩 업데이트 해주자.

마지막 N개의 인풋들을 수열 \(a_i\)라고 하면 \(a_0\)는 반드시 0이다.
근데 0이 될 수 있는 후보들은 전체가 돼버린다. 따라서 처음부터 처리하지 말고 끝에서부터 처리해야 한다.
가령 TC처럼 마지막이 4라면 모든 값이 있는 상태에서 본인보다 작거나 같은 값의 갯수가 4개여야 한다.
그렇다는건 본인은 크기순으로 5번째에 위치한 숫자여야 한다! 따라서 이 숫자를 스택에 넣고 세그트리에서 값을 삭제한다.
그렇게 모든 \(a_i\)를 처리한 후에는 스택에 담긴걸 top부터 쭉 출력해주면 된다.

BOJ 10090: Counting Inversions

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

solution

입력받는 값의 상한이 \(10^6\)이므로 세그트리의 인덱스로 활용해 업데이트할 수 있다.
현재 값이 x라면 인덱스 x에 1을 업데이트하고 [x+1, n]의 구간합을 답에 매번 갱신해주자.
시간 복잡도는 \(O(nlogn)\)이 된다.

BOJ 1306: 달려라 홍준

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

solution

일정한 길이의 구간별로 최댓값을 요하는 문제다.
최댓값 취하는 세그먼트 트리로 쿼리를 처리해주면 된다. 기본 유형.

BOJ 18436: 수열과 쿼리 37

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

solution

세그먼트 트리를 2개 쓰자!

BOJ 1777: 순열복원

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

solution

위에서 푼 BOJ 2465: 줄 세우기와 푸는 방식이 비슷하다.
설명만 읽으면 i번 뒤의 값들만 고려해서 처리해야할 것 같지만 반대로 앞으로 기준을 뒤집어보자.
TC에서 입출력이 왜 저렇게 나오는지 처음에 이해가 안가서 정말 답답했던 문제.. ㅡㅡ

BOJ 16978: 수열과 쿼리 22

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

solution

세그먼트 트리는 세그먼트 트린데 쿼리 순서를 연산하기 편하도록 임의로 바꿔서 계산하기 때문에
오프라인 쿼리 유형으로 분류된다.

어떤 방법이 정석인진 모르겠으나 예전에 오프라인 쿼리중 하나인 Mo’s Algorithm을 공부하면서 썼던
코드를 가물가물 떠올려가며 구현을 대충 해봤다. 구간합을 구하는 세그먼트 트리는 코드상 변한게 없다.

BOJ 12846: 무서운 아르바이트

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

solution

BOJ 6549: 히스토그램에서 가장 큰 직사각형과 같은 문제.

BOJ 17952: 과제는 끝나지 않아!

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

solution

늦게 들어온 과제가 있으면 그 과제부터 다시 처리하도록 해야하므로 스택을 이용한다.
주의할 점은 이미 처리하고 있는 과제가 있다면 어떤 쿼리든 상관없이 카운트해줘야 한다.

BOJ 17949: Drop The Byte!

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

solution

단순 구현 문제라고 생각하는데.. 범위가 커서 그런지 vector erase로는 TLE를 받았다.
편하게 하려고 요령있게 해보려다 컷당하고 현재 위치를 의미하는 변수 now를 선언해 위치를 갱신시켜줬다.
별도로 변수를 써도 생각보다 그렇게 까다롭진 않은 듯 하다. 안까다로워야 한다. 이거 브론즈 문제다.. ㅠㅠ

BOJ 17944: 퐁당퐁당 1

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

solution

단순 수학 문제다.
T가 꽤 크므로 모듈러 연산을 통해 크게 감소시켜야 하는데 무턱대고 4N으로 나누지 말고 TC를 더 파보자.
언제 1번 자리로 초기화가 되는지를 체크해봤다면 알겠지만 (4N-2)로 모듈러를 걸어주면 된다.
문제가 뭔 소린지 모르겠어서 설명읽는게 더 힘들었다. 하하..

BOJ 1660: 캡틴 이다솜

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

solution

DP 문제다.
난이도가 실버여서 사실 되게 간단할줄 알았다. (간단한데 내가 복잡하게 푼거 같기도 하다)
1, 1+2, 1+2+3, … 을 sum()으로 만들면 점화식은 간단하게 sum(n-1)+n이 된다.
그리고 이 sum()을 위의 점화식처럼 하나 더 만들면 ssum(n) = ssum(n-1)+sum(n)이다.
ssum(n)은 크기가 n일 때 한 더미에 필요한 대포알의 갯수이다.
이렇게 구한 ssum()을 최종적으로 f()에서 활용하는데, f(n)은 대포알이 n개 있을 때 만드는 사면체의 최소 갯수다.
현재 갖고있는 대포알의 갯수(cur)를 넘지않는 ssum(i)을 cur에서 빼주면서 답의 갯수를 1씩 카운트하도록 한다.
그렇게 구한 각 경우의 수에서 얻은 답중 최솟값을 출력하면 된다.

문제를 잘못 읽어서 좀 고생했다.

BOJ 2665: 미로만들기

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

solution

다익스트라로 풀었다.
시작점부터 끝점까지 도달하는데 거치는 벽의 최소 개수를 구해야 하는데 문제만 딱 보면 전형적인 BFS가 떠오른다.
다익스트라도 BFS를 쓰긴 하지만.. 여기서 말하는 전형적인 BFS는 이런 문제들을 말한다.
생각을 좀 해보면 정말 깔끔하게 풀 수 있는데, 각 점에서 이웃한 점에 엣지를 놓으면서 용량은 벽이 있으면 1, 없으면 0으로 두자.
그리고 시작점에서 다익스트라를 돌리면 끝점까지 최단 경로로 도달하므로 거치는 벽의 갯수를 최소화할 수 있다.

BOJ 17946: 피자는 나눌 수록 커지잖아요

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

solution

최대한 많은 공간을 가르도록 자른다고 가정하면 갈 수록 1칸씩 더 많이 가로지를 수 있다.
이해하기 쉽게 공간을 가르지른다고 생각하지 말고 칼질한 선과 마주치는 횟수라고 해보자.
그럼 처음 칼질할 땐 0번 마주치고, 그 다음엔 1, 2, … k번만큼 마주치게 된다.
선을 마주친 횟수+1 만큼 새로운 공간(피자 조각)이 생기므로 조각의 갯수는
처음이 1이라 하면 1, 2, 4, 7, 11, … 로 커지게 된다.
근데 칼질한 횟수를 계속 더해가면서 조각을 내놓으라고 하고 있으므로 갯수는 다음과 같아진다.

조각 : 1 2 4 7 11 ...
내놔 : 0 1 3 6 10 ...

즉 언제나 먹을 수 있는 조각 수는 항상 1개가 된다. 최대라는 말은 약간의 함정(?)이다.
예찬이가 불쌍하다.

BOJ 17954: 투튜브

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

solution

2개의 튜브 양끝의 구멍 총 4개중 제일 작은 값을 계속 빼내면서 누적되는 부패도를 갱신해야 한다.
부패도는 누적 시간과 남은 숫자들의 합을 서로 곱한걸 의미한다.
시간은 어차피 흘러갈거고 남은 숫자들의 합만 컨트롤할 수 있는데 그렇다면 큰 숫자가 먼저 사라지는게 이상적이다!
그러므로 2N, 2N-1, 2N-2, 2N-3은 바깥 구멍 4자리에 모두 위치하도록 하자.
그 다음엔 어차피 2N-3이 사라지면 그 행의 중간에 있던 수들은 뭐가 있던간에 모두 차례대로 사라지게 된다.
그럼 기왕 사라지는거 큰 수부터 사라지는게 좋으므로 큰 값부터 줄줄이 나열해주자.
아직 채워지지 않은 행도 위에서 한 방식대로 채워주자.

대충 이런 식이다.
2N-3 [2N-4 ... N-1] 2N-1
2N-1 [N-2  ...   1] 2N


구현이 생각보다 어렵다.

BOJ 17945: 통학의 신

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

solution

-1000부터 1000까지 다 조사해주면 된다.

BOJ 17950: 스노우볼

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

solution

단순 수학 문제다.
오버플로우 및 모듈러 연산에 주의.

BOJ 17953: 디저트

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

solution

DP로 풀었다.
현재 먹어야 하는 디저트의 번호를 cur, 이전에 먹은 디저트의 종류를 prev라 설정했다.

BOJ 13699: 점화식

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

solution

DP 기본 문제. 설명에 점화식이 쓰여있으니 구현만 하면 된다.

BOJ 17626: Four Squares

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

solution

DP 기본 문제. 현재보다 작은 제곱수를 빼주는 경우의 수를 메모이제이션으로 구하자.

BOJ 17942: 알고리즘 공부

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

solution

BFS + 이분 탐색으로 풀었다.
\(1\leq K_i \leq 10^8\)이므로 이분 탐색 범위를 \([1, 10^8]\)로 잡는다.
최소 M개의 알고리즘을 배울 수 있는 시간 x를 이분 탐색으로 찾아주면 된다.
BFS에서 1개가 업데이트 됐을 때 업데이트된 대상에 대해서만 단축된 시간이 조건에 맞는지만 체크해주면 된다.
(업데이트 됐다고 모든 케이스를 돌아볼 필요가 없다는 뜻)

BOJ 17939: Gazzzua

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

solution

우선순위 큐에 값과 인덱스를 같이 넣어 큰 값부터 꺼내도록 설정한다.
처음엔 현재 값의 인덱스보다 작은 위치에 있는 녀석들은 어차피 값이 작으므로 그 갯수만큼 큰 값에 곱해 답에 더해준다.
어디까지 처리됐는지 표시하기 위해 처리된 큰 값의 인덱스를 prev로 표시하도록 하자.
그 다음에 top에 있는 녀석은 2번째로 값이 크겠지만 인덱스가 prev보다 작을지 클지 모른다.
작다면 위 과정에서 처리되는 대상이므로 코인을 산 상태가 돼야 한다. 따라서 답에서 해당 값을 빼주자.
반대로 크다면 prev와 현재 위치(cur.second) 사이에 있는 갯수만큼 값에 곱해 답에 더해준다.
이 과정을 반복해주면 된다.

개인적으로 그리디 문제가 제일 어려운거 같다.

BOJ 17940: 지하철

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

solution

다익스트라로 풀 수 있다.
보통은 최단 거리를 구하는게 기준이지만, 이 문제에서는 기준이 조금 다르다.
최적의 출근 경로란 환승 횟수를 최소로 하는 경로 중 소요시간이 가장 짧은 경로이다.
즉, 환승 횟수를 최소한하는게 우선 순위고 그 다음이 소요시간을 최소화하는 것이다.
때문에 pair<pair<int, int>, int>에서 first인 pair<int, int>는 환승 횟수, 소요시간을 의미한다.
second는 인덱스를 의미한다.

역의 정보는 train[i]에 담았고 이를 이용해 역이 다르면 add를 1, 아니면 0으로 설정하도록 했다.

BOJ 17943: 도미노 예측

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

solution

DP로 구하는 부분합을 구하는 방법을 응용했다.
각 도미노 숫자를 a, b, c, d, e라 하고 인덱스가 1번부터 시작한다고 할 때(0번 도미노 숫자는 0)
인풋을 통해 a^b, b^c, c^d, d^e를 이미 알고 있는 상태다.
1, 3번을 XOR한 값을 구해야 한다면 a^c를 구해야 하는데 이는 (a^b)^(b^c)와 같다.

(a^b)^(b^c) = a^(b^b)^c = a^0^c = a^c

v[i]를 1~i번을 모두 XOR한 값이라 할 때 1번 쿼리는 v[x]^v[y]로 구할 수 있게 된다.

2번 쿼리는 도미노 숫자가 입력으로 들어온다. x의 도미노 숫자가 d일 때 y의 도미노 숫자를 구해야 한다.
x, y번째의 도미노 숫자를 a, b라고 하자. (입력받은 d가 곧 a)
x~y의 XOR은 위의 과정을 통해 v[x]^v[y]로 구할 수 있다.
근데 x~y의 XOR이나 x, y의 XOR이나 같다. 즉 v[x]^v[y]는 a^b가 된다!
이 때 a값을 알고 있으므로 a^b에 a를 XOR해주면 원하는 값 b가 나오게 된다.

사실 XOR 연산에 대해서 깊게 생각해본 적이 없어서 이걸 어떻게 구해야하나 싶다가
TC가지고 장난치다가 우연히 답을 구했다. 운좋게 증명도 할 수 있었다.

BOJ 17947: 상남자 곽철용

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

solution

그리디 유형이다.
cur는 곽철용의 점수를, card는 (선택되지 않은 카드 % k)를 원소로 갖고 있는 배열을 의미한다.
이 때 비교를 하기 쉽도록 card를 내림차순으로 정렬한다.
그 뒤에는 투 포인터로 처리하는데, 왼쪽을 lo, 오른쪽을 hi라 하면 기본값은 각각 0, 1이다.
내림차순이므로 card[lo]는 가장 큰 값부터 시작한다. 이 숫자는 항상 cur보다 크거나 같아야 한다.
그렇지 않다면 뒤에 있는 모든 원소들과의 차이는 항상 cur보다 작고 이는 대상에 포함이 되지 않는다.

for문 안으로 들어오고 나서는 lo, hi가 움직이면서 두 카드의 값 차이가 곽철용보다 큰 경우만 카운트한다.
이 때 총 플레이어 m명중 곽철용을 제외한 m-1이 나머지 플레이어이므로 답은 m-1보다 작거나 같다.

BOJ 17951: 흩날리는 시험지 속에서 내 평점이 느껴진거야

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

solution

최솟값을 \([0, 2 \times 10^5]\) 에서 이분 탐색하면 된다.
매번 임의로 정하는 최솟값을 x라 하면 값을 처음부터 계속 더해가면서 x를 넘으면 카운트한다.
그렇게 카운트 한 수가 cnt일 때 cnt가 k보다 크면 최솟값이 작다는 말이므로 l을 움직이고
그렇지 않다면 r을 움직이도록 한다.

BOJ 1072: 게임

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

solution

승률이 바뀌게 되는 최소 승리 횟수를 구해야 한다.
이분 탐색으로 구할 수 있으며 초기 승률과 같다면 하한을, 다르다면 상한을 움직이면 된다.

BOJ 13306: 트리

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

solution

Union-Find + 오프라인 쿼리 문제.
연결 돼있는지 여부는 두 노드의 부모가 같은지 여부로 체크할 수 있다.
쿼리를 들어오는대로 처리하게 되면 중간에 끊고 업데이트하고 … 복잡해짐과 동시에 TLE라는 선물을 받을 수 있다.
x=0일 때 노드의 직계 부모와의 엣지를 끊는다고 생각하지말고 뒤집어서 연결한다고 생각해보자.
쿼리를 역순으로 실행한다면 오히려 끊지 않고 연결하기만 하면 된다. 두 노드를 하나의 집합으로 묶으면 끝이다.

발상의 전환이 오프라인 쿼리의 또 다른 이름인 것 같다.

BOJ 17069: 파이프 옮기기 2

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

solution

DP 문제다.
현재 파이프의 상태(가로, 세로, 대각선)에 따라 조건을 달리해주면 된다.
BOJ 17070: 파이프 옮기기에서 썼던 코드중 범위, 자료형만 수정했다.

BOJ 14916: 거스름돈

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

solution

DP로 풀었다.
현재 값(cur)에서 5, 2를 빼면서 1씩 카운팅하되 최종 cur이 0이 되지 않는다면 INF를 반환해 거슬러줄 수 없도록 하자.
최종적으로 거슬러줄 수 없는 경우의 수가 존재하므로 유의. 없는줄 알고 제출했다가 틀렸음

BOJ 2410: 2의 멱수의 합

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

solution

이전에 뺀 값을 \(2^prev\)이라 하면 그 다음부터 빼는 값이 \(2^i\)일 때 \(i \leq prev\)여야 한다.
이 부분때문에 cache[1000001]이 아닌 cache[1000001][21]로 설정했는데 이 부분이 메모리를 꽤 잡아먹는다.
오버플로우 때문에 WA받는걸 방지하려고 자료형을 long long으로 놓는게 습관이 됐는데 이 점때문에 메모리 초과를 계속 받았다..

BOJ 11409: 열혈강호 6

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

solution

MCMF 유형 문제다.
비용을 음수로 만들고 MCMF를 돌리면 최소 비용이 아닌 최대 비용을 구할 수 있다!

BOJ 11493: 동전 교환

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

solution

MCMF 유형 문제.
kks227님의 글을 참고하면서 풀어보려고 했는데 열심히 구현하다 막혔다.
하지만 뛰어들기 까지 아이디어를 얻기가 어려웠는데 참고하고 한결 수월해졌다!

정점끼리 유량이 흘러야 하기 때문에 정점을 분리까지해서 꽤 복잡해지고 TC까지 제대로 나와가지고 제출했다가 WA를 받았는데
어디가 잘못됐는지 모르겠어서 정점끼리 유량이 흘러가면서 간선의 비용을 긁어오는 방식은 포기하고
플로이드 알고리즘으로 모든 정점에서 모든 정점으로의 최단 거리를 구해 검은 동전에서 검은 정점의 cost로 사용했다.
최단 거리를 cost로 쓸 수 있는 이유는 이 문제에서는 각 간선의 비용을 1로 설정했기 때문이다.
위와 같은 방법으로 설정하면 원래는 목적지까지 여러 점을 거쳐 도달해야 하지만 이 과정을 생략하고 다이렉트로 갈 수 있다.
물론 플로이드를 써도 충분히 돌아가는 정점, 간선들의 범위 그리고 넉넉한 시간 제한 덕분이다.

BOJ 3980: 선발 명단

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

solution

범위가 작아서 브루트 포스로도 풀 수 있는 모양이지만 연습할겸 MCMF로 풀었다.
START -> 포지션 -> 스텟 -> 사람 -> END로 모델링하고 각 간선의 용량은 1로 설정했다.

BOJ 2311: 왕복 여행

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

solution

MCMF로 풀었다.
정점을 분할한걸 IN, OUT이라 하면 IN~OUT의 간선의 용량은 2로, 이외의 정점끼리 용량은 1로 설정하면 된다.

BOJ 10217: KCM Travel

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

solution

다익스트라로 풀었다.
DP로 분류돼있는 문제만 풀어보는 중이었는데 우연히 이 문제를 발견했다.
보통 다익스트라 문제라고 하면 최단 거리만 찾는데 집중돼있는데 이 문제도 최단 거리(시간)을 찾는건 맞지만
티켓을 이용했을 때 비용이 다 소진되는지 여부를 체크해줘야 한다. 때문에 배열을 2차원으로 늘려서 풀어야 한다.
전반적으로 코드는 다익스트라라는 틀에서 크게 벗어나지 않는다.

BOJ 13698: Hawk eyes

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

solution

단순 구현 문제.

BOJ 16118: 달빛 여우

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

solution

다익스트라 문제다.
여우의 최단 경로는 일반적인 다익스트라를 1번 돌려주면 되고,
늑대는 빠른 경로, 느린 경로를 2개 만들어서 현재 상태에 맞게 다익스트라를 돌려주면 된다.

BOJ 10473: 인간 대포

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

solution

다익스트라 문제.
시작점에서 다익스트라를 돌려 모든 대포로 이동할 수 있는 최단 거리를 계산하고 도착점까지의 거리(걸어서)도 계산한다.
그 다음엔 각 대포에서 도착점으로의 걸어서 가는 거리를 위에서 계산한 거리와 더해 그 값들의 최솟값을 취해 출력한다.

BOJ 17219: 비밀번호 찾기

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

solution

map으로 처리하는 기본 문제.

BOJ 18870: 좌표 압축

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

solution

정렬을 이용해 내림차순으로 순위를 매기고 출력하면 된다.
같은 값은 순위가 같음에 주의.

BOJ 1850: 최대공약수

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

solution

인풋으로 들어오는 a, b값에 대한 최대공약수를 구하고 그 값만큼 1을 출력해주면 된다.

BOJ 2504: 괄호의 값

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

solution

각 괄호 종류에 대해서 쌍이 맞는지부터 체크하고 시작한다. 쌍으로 떨어지지 않으면 0을 출력하고 종료한다.
그 다음에는 재귀를 돌리면서 답을 갱신하는데, 이 때도 올바른 괄호열(설명 참고)이 아니면 0을 출력하고 종료한다.
괄호가 ()라면 prev를 0, []라면 1로 설정했다. 여는 괄호를 (, [이라 하고 그 반대를 닫는 괄호라 하자.

닫는 괄호일 땐 현재 괄호와 prev가 같다면 1을 리턴하고 아니면 0을 출력하고 종료한다. (위에서 설명한 내용)

여는 괄호일 땐 그 안에 있는 괄호열의 값에 2 또는 3을 곱해야 한다. 따라서 그 다음부터 재귀를 한 번 더 돌려준다.
이 때 다음 문자열에서 반환하는 값(next)이 1이라면 더 이상 조사할 필요가 없음을 의미한다. (쌍을 찾은 것과 같다)
그렇지 않다면 임시 결과값인 지역 변수 ret에 더하도록 하고 재귀를 돌려 다음 값을 조사한다.

main에서는 이렇게 재귀로 돌린 값을 답에 갱신해주고 마지막에 출력해주면 된다.

스택으로 풀면 간단하게 풀겠지 싶었는데 적당한 방법이 구체적으로 안떠올라서 결국엔 재귀로 풀었지만
생각보다 난이도에 비해서 되게 골치 아팠다. 시간이 너무 오래 걸렸다..

BOJ 9184: 괄호의 값

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

solution

문제에 적힌 점화식을 따라서 적절하게 구현하면 된다.

Location

Icheon, KR

Email

iteratively@naver.com

Social

-->