1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다.순서대로 K번째 사람을 제거한다.한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다.이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.: 수를 늘여
커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다.길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.명령
문자열 S는 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('<', '>')로만 이루어져 있다.문자열의 시작과 끝은 공백이 아니다.'<'와 '>'가 문자열에 있는 경우 번갈아가면서 등장하며, '<'이 먼저 등장한다.
잘려진 쇠막대기 조각의 총 개수를 구하기.쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.레이저는 어떤 쇠막대기
오큰수 구하기.크기가 N인 수열 A = A1, A2, ..., AN이 있다.Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,0
오등큰수 구하기.크기가 N인 수열 A = A1, A2, ..., AN이 있다.Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한
후위표기식 구하기.후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다.우선 주어진 중위 표기식을 연산자의 우선순위에 따라 괄호로 묶어준다. 그런 다음에 괄호 안의 연산자를 괄호의 오른쪽으로 옮겨주면 된다.첫째 줄에 중위 표기식이 주어진다. 단
연산을 사용하는 횟수의 최솟값 구하기.정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다 1\. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2\. X가 2로 나누어 떨어지면, 2로 나눈다. 3\. 1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하기.정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다.합을 나타낼 때는 수를 1개 이상 사용해야 한다.단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.첫째 줄에 테스
한 개의 회의실을 N개의 회의에 대하여 겹치지 않고 사용할 수 있는 최대 회의 개수 구하기.회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마
백준 4485BFS는 갈 수 있는 곳과 갈 수 없는 곳으로 나뉘어 있다면, 다익스트라는 모두 갈 수 있는데 비용이 적게 들고 우선순위가 큰 곳을 방문한다는 차이가 있다.따라서 다익스트라는 우선순위 큐를 떠올리는 것이 당연한 것이다.맵에서 가중치는 도둑루피를 나타내고,
백준 1504이 문제는 다익스트라 문제로, 1번부터 N번까지 최단경로로 이동해야하는데, 특정한 두 점을 반드시 지나서 가야한다.특정한 두 점 x, y가 있을 때의 최단경로는 1-x-y-N일 수도 있고 1-y-x-N일 수도 있으므로 두 경우를 모두 구하여 최솟값을 출력하
백준 1261
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다.상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.상덕이가 훔칠 수 있는 보석의 최대 가격을 구
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에,
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
최대로 벌 수 있는 돈 구하기.각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은
수빈이가 동생을 찾는 가장 빠른 시간 구하기.수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
수빈이가 동생을 찾는 가장 빠른 시간과 경로 구하기.수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가
수빈이가 동생을 찾는 가장 빠른 시간 구하기.수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일
최대가 되는 연속 합 구하기.n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지
영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값 구하기.영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보
영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값 구하기.각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다.이제 어떤 물통에 들어있는 물을 다
A를 B로 바꾸는데 필요한 연산의 최솟값을 구하기.정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.2를 곱한다.1을 수의 가장 오른쪽에 추가한다. 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.A를 B로 바꾸는데 필요한 연산
당신의 병사의 위력의 합과 적국의 병사의 위력의 합을 출력하기.당신의 병사들은 하얀 옷을 입고, 적국의 병사들은 파란옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다.N명이 뭉쳐있을 때는 N^2의 위력을 낼 수 있다. 과연 지금 난전의 상황에서는 누가 승리할
괄호의 값 구하기4개의 기호 ‘(’, ‘)’, ‘’, ‘’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.한 쌍의 괄호로만 이루어진 ‘()’와 ‘\[]’는 올바른 괄호열이다. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘X’도 모두 올바른
안전 거리의 최댓값 구하기.N×M 크기의 공간에 아기 상어 여러 마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 아기 상어가 최대 1마리 존재한다.어떤 칸의 안전 거리는 그 칸과 가장 거리가 가까운 아기 상어와의 거리이다. 두 칸의 거리는
고이는 빗물의 총량 구하기.2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이
부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이 구하기.10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에
A번째 도시에서 B번째 도시까지 가는데 드는 최소비용 구하기.N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다.도시의 번호는 1부터 N까지이
최소 스패닝 트리의 가중치 구하기.그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.첫째 줄에 정점의 개수 V(1
서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.첫째 줄에 자연수 N의 최댓값을 출력한다.: 1부터 n까지의 합인 n\*(n+1)//2 공식 활용1부터
가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다.이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른
n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.첫째 줄에
i i\`int& a\[]&, b, c\*;\`a의 타입은 int&&\[]\*, b는 int&, c는 int&\*이 된다. 변수의 오른편에 있는 변수형은 순서를 뒤집어서 왼편에 붙일 수 있다. 따라서, int\*& a는 int a&\*와 같다.i\* 입력으로 주어진 변
100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지 구하기.게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다. 보드판에는 1부터
수빈이가 동생을 찾는 가장 빠른 시간과 경로 구하기.네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된
사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 구하기.'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.게임
사과의 위치와 뱀의 이동경로가 주어질 때 이 게임이 몇 초에 끝나는지 구하기.총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니
이동할 때마다 주사위의 윗 면에 쓰여 있는 수를 출력하기크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 전개도는 아래와 같다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값 구하기.인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.연구소는 크기가 N×M인
숫자가 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 수를 구하기.상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만
초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오.첫째 줄에 n(1 ≤ n ≤ 1,000,000
뒤의 입장에서 생각.다이나믹 프로그래밍은 뒤의 입장에서 생각하는 방식이 많은 것 같다. 앞부분의 어느 정도까지는 메모를 해주고, 뒤의 입장에서 앞을 바라본 식을 작성해 dp에 넣어주는 생각을 해야한다.첫번째 계단 올라가는 방법은 한가지.\-> dp에 첫번째 계단의 점수
최대로 마실 수 있는 포도주의 양 구하기.효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.포도주 잔을 선택하면 그 잔
독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.집합 S와 k가 주어졌을 때, 수를 고르는 모든
N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000)
N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.|A0 - A1| + |A1 - A2| + ... + |AN-2 - AN-1|첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다.
민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작했다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)한 줄에 하나씩 문제의 조건을 만족하는
반복문을 사용해 이진탐색의 방법으로 문제를 풀었다. 이진탐색은 반씩 쪼개어 탐색을 하므로 순차탐색보다 훨씬 시간을 줄일 수 있다. 그런데 시간초과가 너무 많이 나서 결국 python3가 아닌 pypy3로 제출하여 통과되었던 문제이다. pypy3가 더 빠르게 수행된다고
입력 종료 조건이 '.'이므로 반복문 안에서 문자열을 입력받고 만약 입력값이 '.'이면 반복문을 종료한다.no 혹은 yes를 출력하기 위한 깃발을 세워준다. 처음 flag의 값은 0인데 짝이 맞는 조건에 부합하지 않으면 flag에 카운트를 해준다.마지막에 flag가 처
입력값을 arr에 넣고 arr의 ele와 스택의 원소를 비교한다.1) 스택의 원소가 없거나 스택의 가장 위의 원소가 ele보다 작으면 ele만큼 수를 넣어준다. 이후 pop2) ele와 스택의 원소가 같다면 pop.\+와 - 를 넣어줄 p배열을 만들고 연산의 가능여부를
백준 1021방법1.
DFS를 이용하여 구현해보았다. 우선 입력받은 값을 DFS를 하기 편하도록 그래프를 만들어주었는데, 연관이 있는 수들은 서로의 리스트에 추가해줘야한다. 방문한 노드를 기록하기 위해 visited 리스트도 만들어주었다.현재노드는 방문처리해주고, 현재노드가 가진 리스트 안
BFS는 큐를 이용하여 구현하는데 덱 라이브러리를 사용하면 유용하다.2차원 리스트 입력받기tomato = \[list(map(int, input().split())) for \_ in range(h)]h행만큼의 리스트 안에 리스트를 만들어줄건데 입력받는 수가 여러개이고
동적계획법은 시간, 메모리가 많이 필요한 경우에 하위 문제를 풀고 결과를 기록하고 문제를 해결하는 방식이다.피보나치를 재귀함수로 구현할 경우 어마어마하게 많은 시간이 걸리기 때문에 0을 참조하는 수를 나타내는 zero리스트와1을 참조하는 수를 나타내는 one리스트를 메
시간초과나기 딱 좋은 문제 -> 이진탐색 이용해보기이진탐색의 폼을 기억해두자!이진탐색 함수를 선언하고, 이진탐색은 start, end, mid 세가지 변수를 사용한다. start<=end인 동안 while문을 반복한다. 또한 이진탐색은 정렬되어있을 때 사용할 수
재귀함수가 오래걸리면 다이나믹 프로그래밍을 생각하자.다이나믹 프로그래밍 -> dp테이블!!입력값이 a,b,c 세개이므로 3차원 리스트를 사용한다.이 부분이 아주 중요하다.!! dpac가 존재하면 바로 리턴해주므로 동일한 값을 계속 연산해야하는 재귀함수와는 비교도 안되게
구하고자 하는 수만큼 dp테이블이 있다면 출력하면 되지만 만약 아니라면, 구하고자 하는 수 까지 dp테이블을 채워주고 출력하면 된다.
1번 집의 색은 2번 집의 색과 같지 않아야 한다.N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.처음에 위의 조건들을 보고 어떻게 문제를 풀어야하나 고민이 많았다. 동적 계획
이 문제는 RGB문제를 풀고, 동적계획법은 이렇게 푸는구나를 알고 나니 어렵지 않게 풀 수 있었다.핵심은 1행->2행 2행->3행 .. 이렇게 생각하는게 아니라,2행->1행 3행->2행 .. 이렇게 생각하는 것이다.2행을 기준으로 1행을 어떤 걸 선택할 때 어떤 값이
백준 11047그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야한다. 그리디 알고리즘
그리디 알고리즘으로 분류되어있던데 정렬때문인가..?이 문제는 값을 입력받아 리스트를 정렬한 후, i번째를 i번째와 i-1번째 값의 합으로 바꾸었다. 그리고 arr의 합을 구해주면 되는 간단한 문제이다.
백준 10828방법1. stack을 사용해서 주어진 조건대로 구현하면 된다.주의할 점은, push 일때만 push 숫자 이렇게 받기 때문에 기본적으로 공백을 기준으로 받아야하고, 0인덱스에는 명령을, 1인덱스에는 숫자를 받아야한다.
백준 9012방법1. 스택, flag을 이용해 VPS를 판별한다.flag와 stack은 input값이 달라질 때마다 초기화되어야 하므로 for문 안에 있음을 주의한다.'('이면 스택에 추가하고')'를 만났을 때 스택이 비어있거나 stack.pop()결과가 '('가 아니
백준 18258 방법1. collections모듈의 deque를 이용
DFS와 BFS를 구현하는 문제이다.파이썬에서 1차원 리스트의 원소만 출력하고 싶을 때는 리스트 이름 앞에 별(\*)을 붙여주면 된다!
: 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는다.전역변수를 쓰는게 좋지 않다고 해서 다음부터는 파라미터로 넘겨주도록 해야겠다. 조건에 맞고 안맞고를 기록하는 것은 flag변수를 통해서 했고 조건에 맞지 않으면 재귀를 통해 범위를
백준 9663
이 문제도 앞에 색종이 자르기 문제처럼 분할정복 방법으로 똑같이 하면 되는데 출력부분을 좀 신경써야한다.처음 좌표의 값을 color변수에 넣고 for문을 돌면서 해당 좌표 값이 color와 다르면 flag를 증가시키고 탈출한다.flag가 0이 아니면 color와 달랐다
이 문제는 동적 계획법으로 푸는 문제인데 증가 뿐 아니라 감소하는 부분도 생각해줘야한다.
처음에는 DFS로 구현했었는데 메모리 초과가 나고 런타임 에러가 났다. 코드상의 문제일수도 있지만 대부분의 경우 BFS가 좀 더 효율적이므로 BFS로 구현했다.출력하는 부분에서 Counter가 아닌 set을 사용할 수도 있다.set은 중복을 허용하지 않으므로, set(
백준 1753
메모리 초과 주의. 15746으로 바로바로 나눠서 넣어줘야 한다.n이 1일 때 1 1개n이 2일 때 11, 00 2개n이 3일 때 111, 001, 100 3개n이 4일 때 1111, 0000, 0011, 1100, 1001 5개n이 5일 때 11111, 00001,