분류 전체보기 (74) 썸네일형 리스트형 [Boj 1947] 선물 전달 http://icpc.me/1947 1947번: 선물 전달경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다.www.acmicpc.net교란순열이다dp[i] = (i-1) * (dp[i-1] + dp[i-2])#include using namespace std;using ll = long long;const int MOD = 1e9;int n;ll dp[1000000 + 5];int main() { cin.tie(0)->sync_with_stdio(0); cin >> n; dp[2] = 1; for (int i = 3; i [boj 1365] 꼬인 전깃줄 icpc.me/1365 1365번: 꼬인 전깃줄첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 ��www.acmicpc.net아이디어는 다음과 같은 조건에서 얻을 수 있다꼬인 전깃줄을 최소로 풀어서 꼬여있는 쌍이 없도록 한다이것이 문제에서 요구하는 것인데 x,y(x>y)에서 각각 a,b로 가는 전깃줄이 있다면b가 a보다 큰 경우에 전깃줄이 있다는 것이 자명하다그렇다면 a[i] = j일때 i에서 j로 전깃줄이 연결되어 있다 생각하면LIS를 구하는 문제가 아닐까?라고 떠올릴 수 있다 코드#include int n;int arr[100000 + 5]; .. 이전 1 ··· 7 8 9 10 다음
