목록백준 (142)
mojo's Blog
문제 링크 => 2201번: 이친수 찾기 (acmicpc.net) 2201번: 이친수 찾기 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 들 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 이친수는 다음과 같은 성질을 갖는다고 한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들어서 1, 10, 100, 101, 1000, 1001, 1010, 10000, ... 와 같은 숫자들이 이친수이다. 그렇다면 이 숫자들을 나열하여 규칙성을 찾아보면 다음과 ..
문제 링크 => 4256번: 트리 (acmicpc.net) 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 트리를 이용한 분할정복 문제이다. 이 문제는 preorder와 inorder가 주어졌을때 postorder를 구하는 문제인데 약간 까다로웠다. 먼저 예시를 살펴보도록 한다. preorder : 3 6 5 4 8 7 1 2 inorder : 5 6 8 4 3 1 2 7 preorder의 맨 앞부분 3은 트리의 가장 위에 있는 노드이다. 그리고 inorder를 살펴보면 3을 기준으로 5 6 8 4..
문제 링크 => 4779번: 칸토어 집합 (acmicpc.net) 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 분할정복 문제이다. 가운데 부분을 3^(N-1) 만큼 빈칸을 출력하게 하고 양 옆을 f(n-1) 을 재귀적으로 호출하도록 하면 정답이다. 풀이 code #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #define INF 1000..
문제 링크 => 19541번: 역학 조사 (acmicpc.net) 19541번: 역학 조사 2020년, 신종 전염병이 유행하여 UCPC국 질병관리본부에서 역학 조사를 하고 있다. UCPC국의 인구는 총 $N$명이며 각각 $1$, $2$, $\cdots$, $N$번의 주민번호가 붙어있다. 질병관리본부는 지금까지 $M$개의 www.acmicpc.net Greedy 알고리즘 문제이다. 이 문제는 시간순으로 모임의 정보가 주어져 있으며 전염된 결과를 제공해주기 때문에 역으로 접근하여 문제를 해결하면 풀리는 문제이다. 즉, 역순으로 해당 그룹에 있는사람들의 전염된 결과를 확인하고 모든 사람들이 전염된 경우와 한 사람이라도 전염되지 않은 경우 두 케이스를 나눠서 보는게 중요하다. 1. 모든 사람들이 전염된 경우 =..
문제 링크 => 19535번: ㄷㄷㄷㅈ (acmicpc.net) 19535번: ㄷㄷㄷㅈ 첫 번째 줄에 주어진 트리가 D-트리라면 D, G-트리라면 G, DUDUDUNGA-트리라면 DUDUDUNGA를 출력한다. www.acmicpc.net 트리를 활용한 경우의 수를 구하는 문제이다. 일단 G-Tree 를 구하는건 굉장히 쉽다. 현재 노드에서 이어져 있는 노드가 3개 이상인 경우 즉, n(n>=3)개로 이어져 있는 경우 G-Tree의 갯수는 nC3 = (n)(n-1)(n-2) / 3! 개이다. 그래서 모든 G-Tree를 구할 때 모든 노드를 방문하면서 n>=3 인 경우 nC3을 더해주면 그만이다. 문제는 D-Tree 이다. parent 노드와 child 노드를 잡으면서 동시에 두 노드가 연결되어 있는것은 분..
문제 링크 => 19538번: 루머 (acmicpc.net) 19538번: 루머 예제 1 0분 : 최초 유포자($1$, $6$번 사람)가 루머를 생성한다. 1분 : $1$번 사람은 $2$, $3$번 사람에게 루머를 퍼뜨린다. $2$번 사람은 주변인 $2$명 중 $1$명이 루머를 믿고 있어 루머를 믿게 된다. $3$ www.acmicpc.net BFS 문제이다. 노드와 노드는 양방향으로 이어져 있으며 문제에서 주변인의 절반 이상이 루머를 믿을 때 본인도 루머를 믿는다는 조건을 고려하여 다음 노드로 방문하도록 하는것이 이 문제의 핵심이다. 1. 배열 rumor[x] 를 설정하여 다음 노드로 이동할 때 rumor[next]++ 를 해준다. ( next 사람이 루머를 믿는 수를 1 증가시킴) 2. rumor[n..