본문 바로가기

분류 전체보기105

9465_스티커 ▶실버1 풀이 여기서 중요하게 봐야할 것은 두 변을 공유하지 않는다는 점이다. 이 점을 참고하여 배열을 arr[i][j], dp[i][j] 두 개 만든다.(i는행, j는 열) ① n = 1이라면, 50 10 dp[0][0]의 값은 50이며, dp[1][0]의 값은 10이다. ② n = 2이라면, 50 10 30 50 dp[0][1]의 값은 dp[1][0] + arr[0][1] = 30 + 10 = 40 dp[1][1]의 값은 dp[0][0] + arr[1][1] = 50 + 50 = 100 이다. ③ n = 3이라면, 50 10 100 30 50 70 여기서부터 살짝 복잡해지는데, dp값이 두 가지 경우일 수 있다. dp[0][2]의 값은 dp[1][1], dp[1][0]의 값 중 큰 값에 arr[0][.. 2023. 1. 16.
1699_제곱수의 합 ▶실버2 풀이 ex) n = 12라면, ① dp[12 - 1*1] = dp[11], dp[12 - 2*2] = dp[8], dp[12 - 3*3] = dp[4] 중 가장 작은 값에 +1한 값이 dp[12]가 된다. 하지만 dp[1~11] 의 값을 알기 위해서는 1부터 1씩 증가하며 dp값을 구하는 작업을 먼저 진행한다. i = 1) dp[1] = 1 i = 2) dp[2]: dp[2 - 1*1] + 1= dp[1] + 1 = 2 i = 3) dp[3]: dp[3 - 1*1] + 1 = dp[2] + 1 = 3 ... 이런식으로 n까지 진행하는 과정에서, i 값에 따라 ①을 진행한다. 또, 주의할 점은 dp의 값을 dp값이 가질 수 있는 최대의 항의 수 개수로 초기화 해야한다. (dp[i] = i) 코드 .. 2023. 1. 13.
11660_구간 합 구하기 5 ▶실버1 풀이 누적 합 이용. 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 3 4 5 3 0 3 4 5 6 4 0 4 5 6 7 => 배열 표 0 1 2 3 4 0 0 0 0 0 0 1 0 1 3 6 10 2 0 3 8 15 24 3 0 6 15 27 42 4 0 10 24 42 64 => 누적 합 표 ex) (2, 2) ~ (3, 4) 의 구간 합 이는 8 + 15 + 24 + 15 + 27 + 42 와 같은데, 누적합을 이용하면 sum[3][4] - sum[3][1] - sum[1][4] + sum[1][1] 임을 알 수 있다. 이를 통하여 (x1, y1) ~ (x2, y2)의 구간 합의 점화식은 sum[x2][y2] - sum[x2][y1 -1] - sum[x1 - 1][.. 2023. 1. 11.
11055_가장 큰 증가 부분 수열 ▶실버2 풀이 기본적으로 dp[i] = arr[i]인 상태에서 arr[j](이전 값) < arr[i](현재 기준값)을 만족할 때, dp[j] + arr[i] 와 dp[i] 중 큰 값을 선택하여 dp[i]에 대입한다. 위의 예제를 표로 나타내면 1 100 2 50 60 3 5 6 7 8 1 101 1 + 2 = 3 max(1, 3) + 50 = 53 max(1, 3, 53) + 60 = 113 max(1, 3) + 3 = 6 max(1, 3, 6) + 5 = 11 max(1, 3, 6, 11) + 6 = 17 max(1, 3, 6, 11, 17) + 7 = 24 max(1, 3, 6, 11, 17, 24) + 8 = 32 dp값 중 가장 큰 값이 답 코드 #include #include #include u.. 2023. 1. 10.
11057_오르막수 ▶실버1 풀이 처음에는 왜 dp인지 이해가 가지 않음 -> 모든 수를 탐색하며 오르막 수인지 확인하는 작업을 하기엔 시간이 너무 많이 걸리기 때문에 dp로 처리 만약 0_ _이면 한 자리가 추가될 때 0 0 _ _ (1가지) 만 가능 1 _ _이면 0 1 _ _, 1 1 _ _ (2가지) 가능 .... 9 _ _이면 0 9 _ _, 1 9 _ _, ~ , 9 9 _ _ (10가지) 가능 이런 식으로 생각하면 자릿수와 맨 앞 자리의 수가 무엇인지를 따져 `dp[i][j] : 맨 앞 자리 수가 j인 i자리의 수의 개수` 로 놓는다. ex) 3자리 수 오르막 수 구하기 3자리 수의 오르막 수의 개수를 구하기 위해서는 dp[3][0] + dp[3][1] + ... + dp[3][9] 을 구하면 되는데 dp[3].. 2023. 1. 4.
2003_수들의 합 2 ▶실버4 풀이 투 포인터를 이용한 문제. 같은 방향으로 L, R가 나아가는 형태이다. 먼저 L과 R은 모두 인덱스 0번째를 가리킨다. A[L] ~ A[R]의 합인 sum이 m보다 작다면 sum의 값을 늘려야하므로 R을 오른쪽으로 한 칸 이동하고, sum이 m보다 크다면 sum의 값을 줄여야하므로 L을 오른쪽으로 한 칸 이동한다. sum == m인 경우는 R, L 모두 오른쪽으로 한 칸 이동한다. R이 N을 벗어나기 전까지 진행한다. 코드 #include #include #include using namespace std; int A[10001]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int l = 0, r = 0;.. 2023. 1. 2.

티스토리툴바