Go Gradually - Repository

[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..