th3_b3st_h4ck3r

dp[i] = 1 * dp[i - 1] + 2 * dp[i - 2] + 3 * dp[i - 3] ... dp[i - K] 위와 같은 점화식으로 dp[N]를 구해야 한다고 생각해보자. 일단 dp를 하나하나 구한다고 하면 총 O(NK)의 시간복잡도가 나올 것이다. 그러나 이를 잘 최적화하면 O(K^3 log N) 안에 dp[N]을 구할 수 있다. 바로 행렬 거듭제곱을 이용하는 것인데, 그 전에 "행렬 곱셈을 한다"가 어떤 의미인지 한 번 해석을 해보도록 하겠다. 다음과 같은 행렬 두 개가 있다고 가정하자. [1, 2, 3] [10] [1, 0, 0] [20] [0, 1, 0] [30] 그리고 위 행렬을 곱하면, 다음과 같은 행렬이 나올 것이다. [1*10+2*20+3*30 = 140] [1*10+0*20+0..

어제 국민대학교에서 알고리즘 경시대회를 개최해 참가했다. 문제는 실버1 ~ 골드2 사이 정도로 나왔고, 난이도가 어렵지 않아 올솔을 할 수 있었다. 그러나 문제가 쉬웠기 때문에 올솔러들이 많이 나와 장려상이나 동상 정도 받을 수 있을 것 같다. 정말 많이 성장했다는 느낌을 받을 수 있던 대회였고, 이 페이스를 유지하며 공부하면 내년엔 은상도 노려볼만 한 것 같다.

코드 #define _CRT_SECURE_NO_WARNINGS #include using namespace std; char str[20001]; int n, k, cnt, found, s1, i, j; int main() { scanf("%d %d", &n, &k); scanf("%s", str); for (i = 0; i 1) { str[s1] = 1; cnt++; found = 1; break; } if (!found) for(j=i+1;j

코드 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int main() { int n, sum = 0, arr[11]; scanf("%d", &n); for (int i = 0; i < 11; i++) arr[i] = 10; for (int i = 0; i < n; i++) { int a, b; scanf("%d %d", &a, &b); if (arr[a] == 10) { arr[a] = b; } else if (arr[a] != b) { arr[a] = b; sum++; } } printf("%d", sum); } · 이 문제는 소의 번호와 위치정보를 가지고 소가 이동했는지 이동을 하지 않았는지 판단하는 문제이다. 이 문제..

코드 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int main() { int n; char str[100001]; scanf("%d", &n); scanf("%s", str); if (n

코드 #include using namespace std; int main(){ int n; scanf("%d", &n); if(n

코드 #include int n, d[110]; /* int f(){ int max, max_num=-2100000000; for(int i=0;imax_num){ max=i; max_num=d[i]; } return max; } */ int main(){ scanf("%d", &n); for(int i=0;i int f(){ . . . } · 또, 배열에 저장 되어있는 값 중 가장 큰 값을 출력하는 것이므로, max 변수를 선언해 int 범위 중 가장 작은 수로 설정한 후, 배열의 모든 값을 탐색하며 만일 그 값이 max값보다 크면 max_num값을 탐색한 배열의 인덱스값로 정하며 최댓값의 위치를 구했다. · 후에 이 max값을 리턴하면 사용자가 입력한 값 중 최댓값을 출력하는 것을 볼 수 있다.