본문 바로가기

알고리즘/백준 & swacademy108

BOJ 11997 - Load Balancing (usaco silver, 차원압축) https://www.acmicpc.net/problem/11997 차원압축 + 2차원 구간합 문제. 차원압축하는 게 어떻게하는지 잘 몰랐는데, https://github.com/kks227/BOJ/blob/master/11900/11997.cpp kks227님 코드를 보며 공부했다. 항상 감사합니다 ㅜㅜ #include #include #include #include using namespace std; int pSum[1001][1001]; inline int rangeSum(int x1, int y1, int x2, int y2){ return pSum[x2][y2] - pSum[x2][y1] - pSum[x1][y2] + pSum[x1][y1]; } int main(){ int N, x[1000].. 2019. 9. 29.
BOJ 11444 - 피보나치 수 6 (행렬곱, 점화식 이용) https://www.acmicpc.net/problem/11444 MOD가 10의 거듭제곱꼴이 아니므로 피사노 주기를 사용할수 없다. 따라서 행렬곱을 이용해야 한다. https://www.acmicpc.net/blog/view/28 설명은 이곳 참고 #include #include using namespace std; typedef long long ll; typedef vector matrix; const ll MOD = 1000000007LL; matrix operator * (const matrix& a, const matrix& b) { int n = a.size(); matrix c(n, vector(n)); for (int i = 0; i < n; i++) { for (int j = 0; j.. 2019. 9. 27.
BOJ 2749 - 피보나치 3 (MOD=10^k꼴일 때 주기 이용) https://www.acmicpc.net/problem/2749 피보나치를 MOD로 나눈 나머지는 항상 주기를 갖는다. (피사노 주기라고 함) 그중 특히 MOD = 10^k (k>2) 인 경우 PRD = 15*10^(k-1)이다. fibo(n)의 값은 fibo(n%PRD)의 값과 같아진다. 피보나치를 dp를 이용하여 풀게되면 O(n)에 풀 수 있으므로 이 방법을 이용하면 O(MOD)라고 볼 수 있겠다. #include #include using namespace std; typedef long long ll; const int MOD = 1e6; const int PRD = 15e5; ll dp[PRD]; ll fibo(int k) { if (k > n; fill(dp, dp + PRD, -1); cout 2019. 9. 27.
BOJ 7535 - A Bug's Life https://www.acmicpc.net/problem/7535 7535번: A Bug’s Life The output for every scenario is a line containing “Scenario #i:”, where i is the number of the scenario starting at 1, followed by one line saying either “No suspicious bugs found!” if the experiment is consistent with his assumption about the bugs’ sexua www.acmicpc.net 각 항이 xor로 묶여있는 2-Sat문제이다. p번 벌레가 q번 벌레와 소통했을 때 둘의 성별이 달라야 한다. 이를 p x.. 2019. 8. 19.

티스토리툴바