https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 처음에 뭔가 수학에서의 조합을 이용해 풀 수 있을 것 같았는데 제 아이디어로는 빌딩 사이로 1개만 넣는 거라 고민 끝에 다른 분들의 아이디어를 참고했습니다. 아이디어 : dp[n+1][l][r] 을 구하자 (n+1 : 전체 빌딩, l : 왼쪽에서 본 빌딩 수, r : 오른쪽에서 본 빌딩 수) 결론부터 말하자면 dp[n+1][l][r] = dp[n][l-1][r] + dp[n][l][r-1] + d..
https://www.acmicpc.net/problem/1765 1765번: 닭싸움 팀 정하기 1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다. www.acmicpc.net 그냥 이름이 재밌어 보여서 풀어보았는데 그래프 문제였습니다. 앞서 푼 문제를 dfs로 풀어서 이번에는 bfs로 풀었습니다. 닭싸움 할 때 팀을 알아야 하는 문제입니다. 최대 팀의 개수를 구하면 됩니다. 친구의 친구도 친구이고, 원수의 원수도 친구입니다. 그리고 팀은 모두 친구로 구성됩니다. 그러므로 원래 친구였던 그래프는 그대로 두고, 원수였던 그래프만 한 단계 건너 탐색하면 됩니다. 그렇게 탐색이 완료된 그래프에서 bfs로 계속 친구들을 탐색하여 탐색이 마무리되면 한 ..
https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 새로 이사 온 곳에 친구가 없어서 풀어 본 문제입니다 ㅠㅠㅠ 문제는 간단합니다. 친구의 친구도 친구로 치는데 이 때 무리들에게 최소 얼마를 줘야 모두 친구가 될 수 있는 지 문제입니다. 먼저 친구 그래프를 만든 뒤, dfs 로 해당 그래프에서 가장 작은 친구비를 요구하는 친구들만 골라 합을 구하면 됩니다. 만약 k보다 합이 크면 Oh no 입니다.
백준 11402 이항계수 4 C++
https://www.acmicpc.net/problem/11402 11402번: 이항 계수 4 첫째 줄에 \(N\), \(K\)와 \(M\)이 주어진다. (1 ≤ \(N\) ≤ 1018, 0 ≤ \(K\) ≤ \(N\), 2 ≤ \(M\) ≤ 2,000, M은 소수) www.acmicpc.net Lucas 정리라는 것을 새롭게 알게 된 문제입니다. Lucas 정리는 nCr % p (p : 소수) 를 쉽게 구할 수 있는 방법입니다. 일반적으로 공식을 이용하거나 ( nCr = n! / ((n-r)! * r!) ) dp 등을 이용해 풀 수 있습니다. (nCr = n-1Cr-1 + n-1Cr 이용한 dp) Lucas 정리는 mCn % p 를 다음과 같이 나타낼 수 있습니다. 여기서 m_i, n_i 는 다음과 ..
https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net SCC를 새롭게 공부할 수 있었습니다. SCC는 A, B, C, ... 노드가 방향 그래프로 주어져있을 때 어떤 노드끼리 순회할 수 있는지를 모아놓은 것입니다. 예를 들어 A->B, B->C, C->A 와 같은 그래프가 주어져있으면 A,B,C는 SCC 입니다. 그리고 A->B, B->C, C->A, A->D 와 같은 그래프가..