목록brute_force (10)
블로그 이사 중입니다 >> gumgood.github.io
6064 카잉 달력
C++11 x == M일 때, x = 0y == N일 때, y = 0으로 생각하면, 연도 year 은 다음을 만족한다 year = x (mod M)year = y (mod N) year = iM + x = jN + y (i, j : nonnegative integer) 이 때, 가 표현할 수 있는 년도는 gcd(x,y)이므로 최대 x*y년도를 표현할 수 있다. 따라서 i와 j의 범위는 다음과 같다 0
Problem Solving/문제 풀이
2018. 11. 13. 13:33
11066 파일 합치기
C++11 기본 아이디어는 brute force인데 중복 부분 문제가 있으므로 memorization을 이용한다. dp[i][j] := i부터 j번째 파일들을 하나로 합치는데 드는 최소 비용 (i < j)sum(i,j) := i부터 j번째 파일들의 크기의 합 (부분합을 전처리로 계산해놓으면 O(1)에 구할 수 있다) 이라고 했을 때, 1) i==j 이면 파일이 하나이므로 dp[i][j] = 0 2) j-i == 1 이면 파일이 두 개이므로 dp[i][j] = sum(i,j) 3) 나머지의 경우, dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i,j)) (i
Problem Solving/문제 풀이
2018. 11. 13. 13:14
1018 체스판 다시 칠하기
C++11
Problem Solving/문제 풀이
2018. 11. 13. 12:26
C++11 1~100 사이 완전 세제곱 수들을 표시해두고 가능한 모든 a,b,c에 대해 다음을 만족하는 d가 있는지 확인한다. a, b, c가 가질 수 있는 수는 각각 n이므로 O(n^3)
Problem Solving/문제 풀이
2018. 11. 8. 15:29
13410 거꾸로 구구단
C++11
Problem Solving/문제 풀이
2018. 11. 7. 12:54
5636 소수 부분 문자열
C++11
Problem Solving/문제 풀이
2018. 11. 7. 12:29
14568 2017 연세대학교 프로그래밍 경시대회
C++11
Problem Solving/문제 풀이
2018. 11. 7. 12:28
6988 타일 밟기
C++11 가능한 모든 공차에 대해 밟을 수 있는 타일의 합을 구해본다.
Problem Solving/문제 풀이
2018. 11. 7. 12:03