Go Gradually - Repository

기본적인 0-1 BFS 문제처럼 보인다.deque를 이용하면, push_front() 및 push_back() 을 이용해 열어야 하는 문의 갯수를 셀 수 있다.근데 단순 최단거리가 아니다.죄수 두명을 탈옥시켜야 한다.탈옥의 정의는, 현재 보여지는 지도 밖으로 죄수가 나간다는 의미이다.우리는 여기서, 지도 밖에 padding 을 한 줄 추가함으로서, 탈옥을 시킬 수 있다.단순히 bfs 하면?다음과 같이, 겹치는 지점을 제외해줘야 한다.근데 두개의 거리를, 중복 없이 어떻게 잴 수 있지?시나리오를 그려보며, 규칙성이 있는지 탐색해보면 반드시 어딘가에서 죄수 2명과 외부지점이 만날 수 있다.문제를 두번에 나눠서 풀면, 해를 구할 수 있지 않을까?다음과 같은 경우, 두 죄수 사이의 최단 거리는 5이고, 이 최단..

[2213] 트리의 독립집합문제를 천천히 읽어보자.독립집합이란, 모든 정점 쌍이 인접하지 않은 정점들의 집합이라고 한다. 간단하게 그림을 그려보면, 다음과 같은 예시를 들 수 있다.그리고 다음과 같은 애들은 독립집합이 아니다.여기서 문제는 한가지 새로운 정의를 내린다.독립집합의 크기란? 독립 집합 내 정점들의 가중치의 합정점의 가중치는 정수로 주어지고, 10000 이하로 제한되어 있다.우리의 목표는 독립집합을 이루는 경우의 수 중, 가장 큰 "집합 내 원소의 가중치의 합"을 구하는 것이다.문제에 그래프 형태가 트리 구조로 되어있다고 하는데, 여기에서 우리는 중요한 관찰을 할 수 있다.트리구조로 되어있다는 것은,정점 A가 어떤 독립 집합 S에 포함/제외되는 것이 재귀적으로 자기 자신에게 영향을 주는 "사이..

[1475] 방 번호어떠한 사람(기능) 이 필요한가?항상 설명이 너무 복잡하다면, 일단 문제를 단순화해서 보자. → 조건을 몇개 제거해보자.(6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다는 조건을 제외해보자.)만약, 122 라는 숫자를 만들어야 한다면, 플라스틱 세트는 2세트가 필요할 것이다(2를 2개를 수급하려면, 플라스틱 세트 2세트가 필요할 것이고, 3~9까지 각각 숫자 2개씩은 모두 버려질 것이다. 아깝네)만약, 9999라는 숫자를 만들어야 한다면, 플라스틱 세트는 4세트가 필요할 것이다.(9를 4개를 수급하려면, 플라스틱 세트는 4세트가 필요할 것이고, 9를 제외한 나머지 숫자들 각 4개들은 모두 버려질 것이다.)우리는 여기서, 다음과 같은 결과를 찾을 수 있다.가장 ..

[2577]숫자의 갯수세개의 자연수 A, B, C가 주어질 때, A × B × C를 계산한 결과에0부터 9까지 각각의 숫자가 몇번씩 쓰였는가?순서대로, 하나씩 차근차근 풀어보자.어떤 사람이 필요한가?문제의 예제를 분석하며 한번 우리가 직접 세보고, 어떠한 과정을 거쳤는지 생각해보자.A, B, C를 곱한 결과값을 계산한다. 그 결과로 17037300 이라는 숫자가 등장했다.우리는 그 다음, 각 자릿수별로 어떠한 숫자가 있는지를 확인했다.근데 총 10종류의 숫자가 각각 등장한 횟수를 머릿속에서 다 외우고 있긴 어렵기 때문에, 아래에 각 숫자가 몇번 등장했는지를 기록하며 풀었다.최종 결과로 3 1 0 2 0 0 2 0 0 이라는 결과가 등장했다.이때 재미있게 볼만한 정보는 다음과 같다.기존 숫자의 170373..