yeongminb의 PS 블로그

문제 링크 문제 풀이 어떤 정점 $n\leq 21$개, 간선 $m$개의 그래프 위에 원숭이가 살고 있고, 매 턴마다 인접한 정점으로 항상 움직인다. 이때 매턴마다 그래프 위에 정점 하나를 골랐을 때 최악의 경우에도 언젠가는 원숭이를 잡을 수 있는지를 묻는 문제이다. 또 잡을 때까지의 최소 몇 번의 턴이 필요한지와 가능한 실례도 제시해야한다.   일단 문제를 보자마자 생각할 수 있는 것은 가능하기 위해서는 당연하게 이 그래프가 사이클이 없는 트리여야한다는 것이다. 만약 사이클이 있다면 그 사이클 위에 있는 원숭이는 매턴마다 두 가지의 선택지가 반드시 존재하므로 원숭이를 유인할 수 없다. 이는 직관적으로도 자명하다. 따라서 $m$이 $n-1$이 아닐 경우에는 볼 필요가 없어진다.  처음에는 트리인 경우는 모..

문제 링크 문제 풀이 이 문제는 어떤 양의 실수$\leq 10^9$들의 합에 대한 정보와 곱에 대한 정보가 주어질 때 이 수들의 개수로 가능한 최솟값을 출력하는 문제이다. 합과 곱이 주어졌으므로 산술기하 평균 부등식 AM-GM inequality 을 떠올릴 수 있다. 이 실수들의 합, 곱, 개수를 각각 $S, P, N$이라 할 때 다음이 성립한다.$$S \leq N\sqrt[N]{P}$$$$\Rightarrow P \leq (\frac{S}{N})^N$$  따라서 이를 만족하는 $N$의 최솟값을 찾으면 된다. 이때 불가능한 경우를 따지기 위해 $f(N) = (\frac{S}{N})^N$로 두고 미분하여 최댓값을 찾아야한다.$$(\ln_{}{f(N)})^{\prime}=\frac{f^{\prime}(N)}..

문제 링크 문제 풀이  이 문제는 $m\leq 500$ 개의 $10^8$ 이하의 숫자와 $k\leq m$ 이 주어질 때 $m$개의 숫자를 $k$개의 집합을 나누어 그 집합들의 합의 최대가 최소가 되도록 하는 문제이다. 이때 같은 집합에 포함되려면 그 수들이 모두 연속해야하며 원소에 개수가 1개 이상이어야한다. 예를 들어 9개의 수 100, 200, 300, 400, 500, 600, 700, 800, 900을 3개의 집합으로 나눈다고 할 때 100,200,300,400,500 / 600,700 / 800,900 으로 나눠야 최대합이 1700으로 최소가 된다. 참고로 나누는 방법이 여러개인 경우는 앞쪽의 집합의 원소의 개수가 가장 작을 때를 출력해야한다.  일단 $m,k$의 범위가 작아서 백트랙킹을 해야하..

문제 링크 문제 풀이 이 문제는 $4\times 4$ 크기의 그리드에 글자들이 적혀져 있을 때 이 글자들을 이어 만들 수 있는 단어들을 찾는 문제이다. 이때 찾은 단어의 길이에 따라 점수가 주어져 점수가 최대로 되도록 하게 찾기도 해야한다. 주어지는 단어의 개수는 $w \leq 3\times 10^5$이고 단어의 길이는 최대 8이다.  일단 칸의 개수가 16개로 매우 작은 편이기 때문에 DFS로 완전탐색 할 생각을 할 수 있다. 모든 칸에서 최대 $4^8$번 탐색을 하므로 연산 횟수는 $2^{20}$을 넘지 않는다. 그래서 그냥 완전탐색을 하며 중복만 잘 처리해주면 되는 아주 쉬운 문제이다. 참고로 실행시간 절약을 위해 주어진 단어들을 해시 맵 형태로 저장하였다.  코드#include #include #..

문제 링크 문제 풀이 이 문제는 정점의 개수 $N \leq 200$ 이고 간선의 개수 $M \leq 20000$ 인 그래프에서 특정한 정점에 불을 붙여 모든 정점과 모든 간선이 불에 탈 때까지 걸리는 최소시간을 출력하는 문제이다. 어떤 정점에 불이 붙으면  그와 연결된 모든 간선으로 불이 퍼져나간다. 이때 이 간선이 모두 불타는데 걸리는 시간은 그 간선의 길이와 같다. 또한 간선의 양쪽 정점에 모두 불이 붙은 경우는 두 불이 퍼져나가다 만나면 그 간선이 모두 불탄 것이다. 참고로 간선 중에는 양 끝 점이 모두 동일하게 한 정점인 간선도 있다.  처음 한 생각은 일단 모든 정점으로부터 모든 정점까지 최소 거리를 저장하는 것이다. 그렇게 되면 어떤 정점으로부터 불이 시작될 때 어떤 간선이 불에 타서 없어질 ..

문제 링크 문제 풀이 이 문제는 어떤 0과 1로만 구성된 문자열이 주어질 때 그 문자열의 서로 다를 필요는 없는 부분 문자열끼리 XOR연산을 한 값의 최댓값을 출력하는 문제이다. 여러개의 테스트 케이스로 주어지고, 이때 주어지는 모든 문자열의 길이의 합은 $10^7$을 넘지않아서 $O(N)$풀이가 필요하다.   문제를 처음봤을 때 아이디어가 바로 떠올라서 플레4보단 쉽다고 느꼈는데, 구현을 해볼 수록 고려해야할 게 많다는 것을 깨달았다. 생각한 아이디어는 앞의 나오는 자릿수 중에 1이 많으면 좋으므로, 처음에 나오는 연속한 1들과 그 다음 나오는 0들을 XOR하는 것이었다. 예를 들어 11100010이라는 문자열이 주어지면 11100010과 11100을 XOR하여 앞의 0들을 모두 1로 만들어주어 숫자를..

문제 링크 문제 풀이 이 문제는 $K \leq 50$개의 자연수 중에서 $N\space\space(K \leq N \leq 50)$개의 자연수를 중복을 허용하고 뽑아 이어붙였을 때 만들어질 수 있는 가장 큰 수를 출력하는 문제이다. 이 때 주어진 K개의 자연수 모두 적어도 한 번씩은 사용되어야한다.   이 문제를 접근할 때 두 가지를 고려하였다. 첫 번째는 주어지는 각 숫자의 사용 개수이고, 두 번째는 숫자들의 사용 순서이다. 먼저 각 숫자의 사용 개수는 당연히 자릿수가 가장 많은 숫자를 많이 사용하는 것이 유리하다. 왜냐하면 자릿수가 많을수록 숫자가 커지기 때문이다. 그래서 자릿수가 가장 큰 숫자를 $N-K$번 사용하고 나머지를 1번씩만 사용할 생각을 하였다. 만약 자릿수가 가장 큰 숫자가 2개 이상이..

문제 링크  문제 풀이 이 문제는 Hilbert Curve 모양의 미로에서 시작점까지의 거리가 주어질 때 그 위치의 좌표를 구하는 문제이다. 입력은 $n \leq 2^{15}$ 와 $m \leq n^2$ 이 주어지는데 $n$은 미로의 크기, $m$은 구하고자 하는 점의 시작점으로부터의 거리이다.   Hilbert Curve가 재귀적으로 정의되는 모양이다보니까 이 문제도 재귀적으로 풀어야겠다는 생각을 했다. 이 때 미로를 $\frac{n}{2}$ 크기의 네 구역으로 나누어서 분할정복 알고리즘으로 플 수 있다고 생각했다. 그래서 먼저 좌표를 반환해주는 함수를 다음과 같이 정의해보자.//pair : 크기 k인 미로에서 거리 d인 점의 좌표pair calcCoord(int k, int d)먼저 구하고자 하는 점..

문제 링크 문제 풀이 이 문제는 $1$부터 $N \leq 10^9$까지의 수에서 등장하는 0 ~ 9의 개수를 출력하는 문제이다. 문제 자체는 쉽지만 TLE가 나지 않게 구현을 하려고 하면 조금 까다로운 문제이다.  기본적인 아이디어는 $N$을 각 자리수에 따라 나누어 더블카운팅의 형식으로 세는 것이다. 예를 들어서 $N = 223$이라고 하면 $N$을 200, 20, 3으로 나누어서 0~199까지의 각 자리수의 개수, 0~19까지의 각 자리수의 개수, 0~3까지의 각 자리수의 개수를 따로 세주어 더하는 형식이다. 여기서 0~199까지의 각 자리수의 개수와 같은 경우는 또 0~99, 100~199로 나누어서 생각해볼 수 있다. 10의 거듭제곱 단위로 나뉘기 때문에 이에 대한 정보만 미리 저장해둔다면 빠른 ..

문제 링크  문제 풀이 이 문제는 $N \leq 1.5\times 10^6$일 동안 상담을 하는데 각 상담마다의 걸리는 시간과 얻을 수 있는 금액이 주어질 때 얻을 수 있는 최대 금액을 출력하는 문제이다. 상담을 하는 기간이 서로 겹치면 동시에 할 수 없기 때문에 적절한 상담들만 선택해주어야 한다.   문제를 보자마자 DP가 떠올랐다. 그런데 시작 날짜를 기준으로 DP를 하면 망할 것이 뻔히 보이기 때문에 상담 종료 날짜를 기준으로 DP를 할 생각을 쉽게 할 수 있다. 그러기 위해서 종료 날짜를 기준으로  각 상담들을 정렬해주고 상담의 시작날짜와 종료날짜를 이용해 선분처럼 표현하면 라인 스위핑을 하면서 DP를 해주면 풀릴 것이다.  점화식을 다음과 같이 정의하자. $dp[i] := (i$일 까지 상담을 ..

문제 링크  문제 풀이 이 문제는 $N \leq 10^{5}$개의 행성의 좌표 $x,y,z$가 주어지고 두 행성 $A(x_{A},y_{A},z_{A})$와 $B(x_{B},y_{B},z_{B})$ 의 거리가 $min(|x_{A}-x_{B}|,\space |y_{A}-y_{B}|,\space |z_{A}-z_{B}|)$로 정의될 때 모든 행성들을 연결하는 경로의 최소 길이를 구하는 문제이다.  처음 보자마자 당연하게 MST를 구해야겠다는 생각이 떠오른다. 그런데 MST를 구하는 Kruskal Algorithm을 쓰려고 하면 모든 간선의 개수가 ${N \choose 2}$개이므로 MLE랑 TLE가 날 수밖에 없다. 그래서 간선을 되도록 조금만 저장하는 방향으로 생각해볼 수 있다.  어짜피 MST에 포함되는 ..

문제 링크 문제 풀이 이 문제는 $N\leq 3\times 10^5$개의 보석과 $K\leq 3\times 10^5$개의 가방이 주어지고, 각 보석의 무게 $M_{i}$, 가격 $V_{i}$와 가방에 담을 수 있는 최대 무게 $C_{i}$가 주어질 때 담을 수 있는 보석의 최대 가격을 출력하는 문제이다.   일단 당연히 최대 가격을 얻기 위해선 보석들 중 가격이 높은 순서대로 가방에 넣는 것을 시도해야 한다. 그래서 그리디 알고리즘으로 생각해보면 가격이 높은 보석들부터 가방에 넣는데, 그 가방의 무게는 보석의 무게를 넘는 최소의 무게(lower bound)일 수록 좋을 것이다. 만약 만족하는 가방이 없거나 이미 보석을 넣은 상태라면 넣지 못할 것이다. 이렇게 생각하면 일단 보석에 대해 iteration을..

문제 링크  문제 풀이  이 문제는 수직선 위에서 가로등의 위치들이 주어질 때 각 수직선 상의 위치마다 밝기를 작은 것부터 $K \leqslant 3\times 10^5$개 출력하는 문제이다.   일단 $ L \leqslant 10^{18} $ 이므로 배열에 각 위치들을 배열에 저장하거나, 완전탐색을 할 경우 MLE나 TLE가 날 수밖에 없다. 그래서 필요한 위치들의 밝기만 저장하거나 다른 방법이 필요하다.  가장 처음에 생각했던 것은 인접한 가로등 사이의 구간 길이를 저장하는 것이다. 구간의 길이의 개수는 항상 $N+1$개이고, $N \leqslant 3\times 10^{5} $ 이기 때문에 완전탐색을 해도 별 문제가 없고, 구간의 길이가 각 위치들의 밝기를 특정해주기 때문이다. 예를 들어서 구간의 ..

문제 링크 문제 풀이 이 문제는 Knapsack Problem과 문제 유형은 비슷하지만 고려해야할 게 4개나 되서 조금 더 까다로운 문제이다. 배낭 문제 처럼 DP를 하려고 하면 적어도 변수가 5개인 5차 점화식이 필요해서 막막할 수 있다. 근데 $N ≤ 15$ 로 상당히 작기 때문에 백트랙킹 $O(2^N)$으로 노가다해도 시간 초과가 나지 않을 것으로 보인다. 그래서 걍 백트랙킹만 조건에 맞춰서 잘 구현해주면 끝난다.  백트랙킹을 할 때 모든 재료에 대해서 포함할지, 포함하지 않을 지 두 가지 경우만 신경써주면 되서 크게 어렵진 않지만 종료조건은 조금 까다로울 수 있다. 문제의 출력 조건을 보면 같은 비용의 집합이 하나 이상일 때 사전 순으로 가장 빠른 것을 출력해야한다라고 되어있다.  이것 때문에 틀..

문제 링크 문제 풀이 이 문제는 $N\times M$ 칸에 숫자들이 적혀 있을 때, 테트로미노 타일을 이용해 타일이 포함하는 수들의 합의 최댓값을 구하는 문제이다.  여기서 테트로미노는 폴리노미노의 한 종류로 네 개의 정사각형이 변끼리 인접하여 만들어지는 도형을 의미한다.    $N,M ≤ 500$ 이라서 그냥 브루트포스로 모든 점들에 대해서 백트랙킹으로 탐색해줘도 충분하다. 이때 시간복잡도는 $O(MN)$인데, 정확히는 백트랙킹 할 때 최대 $4^4$ 개의 가짓수가 있어서 $256MN$만큼의 연산이 필요하다.  먼저 Back Tracking 함수를 먼저 구현해보자. 초기 좌표와 깊이, 그리고 현재까지 숫자의 합을 매개변수로 하였다.void BT(int x, int y, int depth, int k){..

문제 링크 문제 풀이 이 문제는 그래프가 주어질 때 서로 연결되어있는 정점이 없도록 최대한 많은 정점을 선택하는 문제이다. 처음 보자마자 이색 염색이 떠오르긴 했지만 홀수사이클이 존재하는 경우에는 이색 염색이 안되므로 다른 방법으로 해야한다.  Case 1) 쪽방이 아예 존재하지 않는 경우(∀$C_{i} = 0$)N = 1 → 1마리N = 2k or N = 2k+1→ k마리 Case 2) 쪽방이 존재하는 경우 먼저 당연하게 쪽방의 개수가 1개 이상인 칸에 경우 쪽방에만 개미를 배치하는 것이 유리하다. 그럼 쪽방에 있는 방을 기준으로 구간을 나누어볼 수가 있다. 문제의 예시에서는 쪽방이 존재하는 방은 1, 4, 6으로 3개이다. 이 3개를 기준으로 구간이 3개로 나뉘게 된다. 이때 1,4,6에는 쪽방에만 ..

문제 링크  문제 풀이 이 문제는 문제에 나온 격자칸에서 두 사람이 게임을 진행할 때 각 칸에 따라 선공이 이길지 후공이 이길지 판단하는 문제이다. 이런 유형의 문제는 게임이론에서 winning state와 losing state를 설정하는 것으로 풀 수 있다. 간단히 말하면 winning state는 받았을 때 이기는 게임의 상태를 의미하고 losing state는 받았을 때 지는 게임의 상태로서 재귀적으로 정의된다. 예를 들어서 상대가 마지막에 $(N-1,M)$칸으로 돌을 이동시켰다면,  $(N,M)$으로 칸을 이동시킬 수 있으므로 $(N-1,M)$은 winning state로 정의 된다.winning state : 갈 수 있는 칸 중 losing state가 적어도 하나 존재하는 칸   (선공이 이..

문제 링크  문제 풀이 누가 봐도 위상정렬을 사용하는 문제이지만 처음 보자마자 그냥 dp로 풀 수 있을 것 같아서 dp로 시도해보았다. 일단 유향그래프니까 각 점에서 들어오는 선분에 연결된 점들을 graph에 저장해주었다. 또 time이라는 배열에 각 건물을 짓는데 걸리는 시간을 저장하였다. dp를 아래와 같이 정의하자.$dp[i] :=$ 건물 $i$를 건설완료 하는데 드는 최소 시간 그러면 아래와 같은 점화식을 얻을 수 있다.  시간복잡도는 $O(NK)$이므로 dp로 해도 시간초과는 나지 않을 것이다. 시행 착오 문제에서 여러개의 테스트 케이스가 주어지는데 각 테스트 케이스마다 graph를 초기화하지 않았다. 근데 신기하게도 예제 1번은 통과해서 조금 고민했었다. 그리고 graph를 초기화해야한다는 사..

문제 링크   "물리학" 카테고리에 있는 문제들을 풀어보다가 이 문제가 재미있게 생겨서 풀어보았다. 예전에 이런 충돌수에 관련된 문제를 3Blue1Brown 이라는 굉장히 좋은(?) 채널에서 본 적이 있다.유튜브 영상 이 영상에서는 두번째 물체의 질량이 100의 거듭제곱 꼴일 때 충돌횟수가 π의 앞의 자리수가 되는 이유를 설명해주고 있는데 예전에 흥미롭게 봤던 경험이 있어서 생각이 났다.  1. 문제 풀이 먼저 알아야할 것은 두 번째 물체의 초기속력이 0만 아니라면 충돌수에 영향을 주지 않는다는 것이다. 만약 첫 번째 물체의 초기속력이 있었다면 상관이 있겠지만 첫 번째 물체의 초기속력이 0이므로 두 번째 물체가 어떤 속력을 가지든 속력비율은 항상 일정하기 때문이다. 근데 소수점계산에서 오류가 발생할 수도..

문제 링크   백준에서 대회 문제들을 찾아보다가 이 문제를 발견했는데 실버1이기도 하고, 재미있게 생겨서 시도해보았다.   문제 풀이 문제는 $m\space\times\space n$ 격자칸에 알파벳들이 적혀있을 때 인접한 칸끼리 이어서 만들 수 있는 $YOKOHAMA$의 개수를 묻고 있다. $m$과 $n$이 모두 $10$ 이하여서 알파벳이 최대 $100$개까지 밖에 없다. 이런 문제는 노가다로 풀어도 괜찮아보인다. DFS로 Y부터 출발해 가능한 모든 경우를 탐색해보자.  1. 입력입력 부분에서는 $m$과 $n$을 입력 받고, table 배열에 $m\space\times\space n$ 격자판을 저장하자. 또, vector에 pair형태로 Y의 모든 좌표들을 저장해주자.char table[11][11];..

문제 링크   문제 풀이 이 문제를 처음 도전할 때는 모든 사대에 대해서 잡을 수 있는 동물들을 카운트 해주는 Brute Force 방법을 쓸 수 있다(시간복잡도 $O(MN)$. 그렇게 하면 $M$과 $N$이 $10^{5}$이하이기 때문에 시간초과가 날 것이다. 그래서 다른 방법을 생각해보면 이분탐색이 떠오른다. 모든 동물에 대해서 조건을 만족하는 사대를 이분탐색으로 찾아주면 시간복잡도 $O(MlogN)$으로 시간초과가 나지 않을 것이다. 조건은 사대와 동물 사이 거리가 L보다 작은 것이므로 아래와 같이 정리할 수 있다.$|x - a| + b ≤ L ⇔ |x - a| ≤ L - b$$⇔ b - L ≤ x - a ≤ L - b$$⇔ a + b - L ≤ x ≤ a - b + L$ 각각의 동물의 좌표 $(a..

문제 링크  문제 풀이 이 문제는 원 위에 정$D1$각형부터 정$D2$각형까지 그릴 때 중심에서 다른 점들에 의해 '가려지지 않는' 점들의 개수를 묻는 문제이다.  제한시간이 1초이고 $D2$가 $2000$이하이므로 넉넉하게 $O(n^2)$으로 해도 별 문제가 없을 것 같아보인다. 반지름이 $D1$인 원에서 부터 반지름이 $D2$인 원까지 각각의 원에 대해서 각각의 좌석들에 대해 모두 탐색을 해보자.각 원에서 좌석들에 그에 대응하는 분수를 대응시켜보자. 이러면 분수를 기약분수로 나타내었을 때 값이 같은 좌석들끼리는 서로 같은 직선상에 있다는 것을 알 수 있다. 따라서 이를 이용해서 문제를 접근하면, 구하는 값은 등장한 기약분수의 종류이다. 코드#include #include using namespace ..

문제 링크 문제 풀이 이 문제는 초기 위치에서 시작해, 이전 변위와 현재 변위의 차가 1 이하가 되도록 이동하여, 마지막 위치까지 이동했을 때 이동 횟수의 최솟값을 묻는 문제이다. $i$번째 이동에서의 이동거리를 $D(i)$로 정의해보자. 이제 각각의 이동에 대해 $D(i)$를 최대로 할 수 있게 Greedy방법을 써보자. 현재 위치 $current$에 대해 $D(i)$로 이동하려면         (a) 남아있는 거리 $d$는 적어도 $1 + 2 + ... + D[i]-1$보다는 커야한다.조건 (a) 를 만족해야함이 자명하다(변위는 1씩 감소할 수 있는데 마지막에 변위가 1로 끝나야하므로) . 또, $D(i)$는 이전 변위 $D(i-1)$에 의해서 결정되는데, 둘의 차이는 항상 1보다 작거나 같다. 따라..

문제 링크  문제 풀이 이 문제는 이분 탐색을 사용하는 전형적인 문제이다. 랜선의 길이를 이용해서 이분 탐색을 하면 된다.  먼저, 왼쪽 포인터를 $L$, 오른쪽 포인터를 $R$라고 했을 때, 초기 값은 $L=1,  R$은 랜선의 길이 중 최대 길이로 지정한다. 이제 이 둘의 평균인 $M$을 보면 두 가지 경우가 있다.1. M의 길이로 랜선들을 나누었을 때 가능한 최대 개수가 N미만인 경우(색칠된 영역에 존재하지 않는 경우)2. M의 길이로 랜선들을 나누었을 때 가능한 최대 개수가 N이상인 경우(색칠된 영역에 존재하는 경우) 먼저 1번 케이스의 경우 $M$이 더 짧아져야하므로 포인터 $R$을 $M$위치로 이동시킨다. 2번 케이스의 경우에는 $M$이 구하는 정답이 될 수도 있지만 조건을 만족시키면서 $M$..

문제 링크  문제 풀이 이 문제에서는 사진틀의 개수와 추천횟수를 주고, 어떤 학생들을 추천했을 때 사진틀에 있는 사진들이 바뀌어 최종적으로 어떻게 되는지 묻고 있다.  나는 이 문제를 풀 때 여러 함수를 정의해서 풀었다. 먼저 사진틀에 사진들이 다 차있는지를 알아보는 full()과, 삭제할 학생을 찾는 remove(), 매 추천마다 사진틀의 시간을 더해주는 addTime()함수를 정의하였다.  먼저 full()함수는 비어있는 것이 존재할 경우 false를 리턴하고, 아닌 경우 true를 리턴하면 되기 때문에 어렵지 않다. remove()함수는 사진틀에 있는 학생들의 추천횟수를 비교해, 추천횟수가 최소인 학생을 찾아주면 된다. 근데 만약 이전까지의 최소와 같은 추천횟수를 갖는 경우에는 걸려있던 시간이 더 ..

문제 링크   문제 풀이 이 문제에서는 좌석들의 정보(VIP여부)가 주어졌을 때 가능한 모든 좌석 배치의 경우의 수를 묻는 문제이다.   당연히 VIP 좌석 때문에 나눠진 좌석들끼리는 서로 영향을 주지 못하기 때문에 각각의 경우의 수를 구하고 곱해야겠다는 생각을 했다. 또 이 가능한 경우의 수는 DP를 이용하면 쉽게 구할 수 있었다. $n$명의 사람이 있고, VIP가 없을 때 가능한 좌석 배치를 $D[n]$ 이라고 하면, 처음 1과 2가 자리를 바꿀 때 나머지 남은 사람이 $n-2$명이므로, $D[n-2]$ 이고, 처음 1과 2가 자리를 바꾸지 않을 때는 1을 제외하면 $n-1$ 명이므로 $D[n-1]$ 이다.$D[n] = \begin{cases}D[n-1] + D[n-2] & n>2\\2 & n = 2..

문제 링크   문제 풀이 문제에서는 볼들의 배열이 주어졌을 때 같은 색깔의 볼들을 한 쪽으로 모으는 최소 이동 횟수를 요구하고 있다.   처음 봤을 땐 왼쪽으로 빨간색을 다 모으는 경우, 파란색을 다 모으는 경우, 오른쪽으로 빨간색을 다 모으는 경우, 파란색을 다 모으는 경우 모두 나눠서 반복문을 4번 돌아 구한 다음, 최소를 출력하려고 했다. 근데 더 생각해보니 왼쪽이랑 오른쪽으로 총 2번만 반복문을 돌아도 다 구할 수 있었다.  핵심 아이디어는 어떤 방향으로 어떤 색을 모을 때의 최소 조작 횟수를 세는 것이 그 방향으로부터 연속하지 않는 그 색의 볼 개수를 세는 것과 같다는 것이다. 예를 들어서 문제의 예시에서 R을 모두 왼쪽으로 넘기는 최소 조작횟수는왼쪽 끝에 연속해 있지 않은 R들의 개수와 같다...

문제 링크   문제 풀이 미로가 주어진 경우에 최단 경로를 구하는 문제이다.   아주 간단하게 최단경로를 구하는 문제이므로 BFS를 생각해볼 수 있다. 미로 상태를 2차원 배열 map에 bool 형태로 저장해두고(1 : true, 0 : false) $(1,1)$에서부터 $(N,M)$까지 true인 경우에만 탐색을 진행하면 된다.   시행착오 한 점으로 이동하는 방법이 여러가지일 수 있는데, 최소로 가는 경로로 업데이트 해주는 작업을 빼먹어서 값이 이상하게 나왔다. 다행히 한 번 컴파일 하고 알아차려서 디버깅하는데 시간이 적게 걸렸다. 코드#include #include #include #include using namespace std;bool map[102][102];int dis[101][101];..