Algorithm45 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. 21921_블로그 ▶실버3 풀이 누적 합을 이용한다. 예제 1번을 예시로 들면 n = 5, x = 2 1 4 2 5 1 1 5 7 12 13 로 누적 합을 구한다. 이때, x = 2이므로 arr[i] - arr[i - 2]를 한 값들을 벡터에 넣고 내림차순 정렬한 뒤 최댓값이 몇 개 있는지 센다. 벡터에 들어가는 값은 6, 7, 6인데 실제로는 5, 6, 7, 6이어야 한다. 따라서 배열 맨 앞에 0을 넣고 구하는 것이 맞다. 코드 #include #include #include #include using namespace std; int visitor[250001]; vector sum; bool compare(int i, int j) { return j < i; } int main(void) { cin.tie(0); .. 2023. 1. 1. 2583_영역 구하기 ▶실버1 풀이 2차원 bfs문제. 점을 기준으로 탐색하는게 아니라 영역기준이므로 다음과 같은 형태로 정사각형 네 꼭짓점 중 왼쪽 아래를 기준으로 잡는다. x, y 값이 주어지면 for문으로 해당 범위 내의 arr[x][y]의 값을 true로 바꿔준다. 모든 범위가 주어지고 나면 (0, 0)부터 (n - 1, m - 1)까지 돌며 bfs 실행. 코드 #include #include #include #include #include #include #include #include using namespace std; queue q; int r[4] = { 1, -1, 0, 0 }; int c[4] = { 0, 0, 1, -1 }; bool arr[251][251]; int land; vector ans; in.. 2022. 11. 11. 3184_양 ▶실버1 풀이 2차원 bfs문제. 울타리 안 한 영역마다 bfs를 돌려주고 그 영역 내의 양 수와 늑대 수를 세서 양 > 늑대 일 경우 양 수를 더해주고, 양 tmpv) { cnto += tmpo; } else { cntv += tmpv; } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int r, c; cin >> r >> c; for (int i = 0; i > garden[i][j]; } } for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (visited[i][j].. 2022. 11. 10. 12847_꿀 아르바이트 ▶실버4 풀이 누적 합을 이용한 문제. 배열 형태로 입력을 받아줄 때 이전까지의 누적 합을 배열에 저장한다. 이후 연속된 m을 더한 것 중 가장 큰 값을 구하는 것이므로 for문을 돌려 arr[i] - arr[i - m] 중 가장 큰 값이 답. 수가 엄청 커질 수 있으므로 자료형은 long long. 0번째 인덱스의 경우를 신경 안써줘서 100%에서 에러났다. 코드 #include #include #include #include #include #include #include using namespace std; long long money[100001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m; .. 2022. 11. 9. 이전 1 ··· 4 5 6 7 8 다음
