FandPROG FandPROG

-합 분해(2225, 백준) 간단한 Dp문제였다.Dp[i][j] = j개의 수를 사용하여 수 i를 만드는 방법의 수로 정의하고 풀었다. >점화식

-방배정(13304, 백준) 간단 한 문제이다. {1~2학년 남녀}, {3~4학년 남}, {3~4학년 여}, {5~6학년 남}, {5~6학년 여}그룹으로 나누어 풀면 된다. 입력 받은수가 어느 그룹에 속하는지를 확인하고 구하면 풀린다. 더보기 #include int low, mid_ma, mid_fe, high_ma, high_fe; int n, k; int main() { int i, j; scanf("%d %d", &n, &k); for (i = 0; i < n; i++) { int x, y; scanf("%d %d", &y, &x); if (1

-쉬운 계단 수(10844, 백준) 간단한 Dp문제이다. Dp[i][j] = 끝이 j로끝나는 i자리 계단 수의 개수로 두고 풀었다. 해보면 기본적으로, Dp[i] = 2 * Dp[i-1]이라는 식이 쉽게 나온다. 하지만 여기서 끝이 0 혹은 9로 끝나는 경우에만 예외가 생기가 되며, 이만 잘 처리해준다면 AC를 맞을 수 있다. >점화식 dp[i][j - 1]) { dp[i][j] = dp[i - 1][j]; way[i][j] = 1; } else { dp[i][j] = dp[i][j - 1]; way[i][j] = 2; } if (s1[i] == s2[j]) { if (dp[i][j] = 0; i--) printf("%c", ans[i]); return 0; } -사전(1256, 백준) 중복 조합 문제이..

-다리 놓기(1010, 백준) 왼쪽 사이트와 오른쪽 사이트사이에 다리를 겹치치 않고 지으려 했을때 가능한 방법의 수를 구하는 문제이다. 몇번 구하다보면 규칙을 발견 할 수있는데, 더 많은 오른쪽 사이트에서 왼쪽사이트를 골랐을 때, 나머지 다리가 더 적은 다리를 구할 수 있게 됨으로 조합으로 나타낼 수 있다. 결국 mCn을 구하는 문제. 더보기 #include long long dp[1010][1010]; int main() { int i, j; int t; dp[0][0] = 1; for (i = 1; i 맨앞에서부터 탐색한다. 현재 N자리값이라면 (N-1)!보다 작아질때까지 (N-1)!을 빼주며 idx를 증가시켜준뒤, 해당 자리값에 저장해 준다. ii) Query 2 -> 지금까지 쓰지않은 수중, 현재..

-수들의 합 7(2268, 백준) 기본적인 세그먼트트리 구간합 문제이다. 세그먼트트리를 구성해준 다음 쿼리마다 연산을 수행해 주면 된다. 범위가 크기때문에 64bit자료형을 사용해야 하고, 문제의 쿼리에서 항상 x > y임이 주어지지 않았음에 주의하자. 더보기 #include #include #include #include using namespace std; long long n, m; long long arr[1000010]; long long segtree[4000010]; long long init(long long s, long long e, long long node) { if (s == e) return segtree[node] = arr[s]; long long mid = (s + e) /..

-선 긋기(2170, 백준) 간단한 그리디 문제였다. 한선분이 다른 선분의 시작점을 포함하고(겹치고)있다면, 두 선분을 하나의 선분으로 합쳐서 보면 된다. 시작점을 기준으로 정렬을 한 뒤, 앞에서부터 탐색해나간다. 선분의 시작이Si, 끝점이 Ei라면, Si가 현재 이어지고있는 선분안에 포함되며, Ei가 그 선분의 끝점보다길면 갱신해주고 아니라면 ans에 선분의 길이를 더해준다. 더보기 #include #include #include using namespace std; int n; int ans; vector vec; int main() { int i, j; scanf("%d", &n); for(i=0;i n) pq.pop(); } } printf("%d", -pq.top()); return 0; } -..

-작업(2056, 백준) ACM craft라는 문제와 똑같다. 순서가 정해져있기에 위상정렬을 떠올릴 수 있다. 기초적인 위상 정렬 문제이다. 위상 정렬에서 진입차수를 제거해갈 때, 해당 노드의 값을 갱신 시켜준다. (선행 노드가 걸리는 시간중 가장 최대 시간이 지난 후, 작업이 가능하다는 점을 생각해보자) 더보기 #include #include #include #include using namespace std; int time[10010], ans[10010], ent[10010]; vector vec[10010]; int n; int main() { int i, j; scanf("%d", &n); for (i = 1; i

최종 순위 문제 https://www.acmicpc.net/problem/3665 원래 등수와 서로 바뀐 등수가 출력 되었을 때의 새로운 등수를 출력하는 문제이다. 만약 확실하지않다면 "?" , 데이터의 일관성이 없어 오류가 발생하는 경우에는 "IMPOSSIBLE"을 출력한다. 입출력 형식 팀의 수 n을 포함하고 있는 한 줄. (2 ≤ n ≤ 500) n개의 정수 ti를 포함하고 있는 한 줄. (1 ≤ ti ≤ n) ti는 작년에 i등을 한 팀의 번호이다. 1등이 가장 성적이 높은 팀이다. 모든 ti는 서로 다르다. 상대적인 등수가 바뀐 쌍의 수 m (0 ≤ m ≤ 25000) 두 정수 ai와 bi를 포함하고 있는 m줄. (1 ≤ ai < bi ≤ n) 상대적인 등수가 바뀐 두 팀이 주어진다. 같은 쌍이..