김머성 블로그

[BAE/<JOON> 문제풀이] 1799. 비숍

https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 핵심:: 완전탐색 최적화 풀이:: 보자마자 생각 할 수 있는 풀이 : 모든 판에 비숍을 배치하며 배치의 유효성을 검사하는 방법이 있다. ( 복잡도 O(2^n) ) 하지만 체스판이 64칸이므로 시간 안에 동작할 수 없다. 아이디어를 떠올리기 : 비슷한 문제 N퀸은 왜 간단하게 풀 수 있었나 생각해보자 퀸은 대각선 뿐만 아니라 같은 종 / 횡에도 하나씩밖에 배치 할 수 없다. 그렇기 때문에 각 행마다 하나의 ..

[BAE/<JOON> 문제풀이] 1562. 계단 수

https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 핵심:: DP 기본 문제 풀이:: 골드 1 치고 점화식이 매우 간단하다. 거기다 힌트에 정답 여부를 거진 확정적으로 확인할 수 있는 내용을 적어놓아서 풀기가 수월했다. 점화식:: DP[n][m][k] = 길이가 n이고 마지막 숫자가 m이며 k의 비트마스크(2^10 - 1) 를 가진 계단수를 만들 수 있는 경우의 수 DP[n][m][k | 1 n; if (n < 10) { cout

[BAE/<JOON> 문제풀이] 2623. 음악프로그램

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 2623:: 음악프로그램 핵심:: 위상정렬 기본 문제 풀이:: 의견:: 코드:: 더보기 #include #include #include #include using namespace std; int main() { int n, m; cin >> n >> m; vector arr(n + 1); vector en(n + 1, 0); for (int i = 1; i > k; int p..

[BAE/<JOON> 문제풀이] 2252. 줄세우기

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 핵심:: 위상정렬 기본 문제 풀이:: 학생 순서가 단편적으로 정해져있고 정해진 순섬나 해치지 않는다면 어떤 순서로 배열해도 상관없다. 그냥 위상 정렬하고 정해지지 않은 순서는 번호 순으로 출력한다. 코드:: 더보기 #include #include #include #include using namespace std; int main() { int n, m;..

[BAE/<JOON> 문제풀이] 7570. 줄 세우기

https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 핵심:: DP문제 풀이:: 일반적인 nlogn LIS 전깃줄 문제 같아 보인다. 하지만 학생을 항상 맨 뒤나 맨 앞으로만 뺄 수 있기 때문에 일반적인 LIS문제로 풀이할 경우 다음과 같은 반례가 생긴다. 1 2 3 5 6 4 위의 예제의 경우 LIS를 구하면 1 2 3 5 6 으로 총 5의 길이를 가지기 때문에 정답이 1로 나오지만 4번 어린이를 3과 5 사이에 삽입하는 것은 불가능하다. LIS를 구하는..

[BAE/<JOON> 문제풀이] 2533. 사회망 서비스

https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 핵심:: 루트노드를 따로 주지 않기 때문에 트리를 양방향 그래프로 생성하고 자식노드는 부모노드를 탐색하지 못하게 하는 방법이 핵심이었다. 풀이:: DFS 탐색의 점화식은 다음과 같다. DP[노드 번호][부모 노드 얼리어댑터 여부] = 필요한 하위 노드 얼리어댑터 총합( 본인 포함 ) 기저 사례는 리프 노드에 도달 했을 경우인데 리프 노드의 경우는 자신의 부모의 얼리어댑터 여부만 보고 DP값을..