본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[BOJ] 백준 9095 1, 2, 3 더하기 출처: https://www.acmicpc.net/problem/9095 Approach n이 크지 않아서 중복조합을 사용할 수 있지만 테스트 케이스 T가 주어지지 않아서 T의 크기에 따라서 결과가 다를 수 있습니다. DP 점화식을 이용한다. DP[i] = DP[i - 1] + DP[i - 2] + DP[i - 3]; DP[1] = 1; / DP[2] = 2; / DP[3] = 4;는 미리 정의 N의 범위가 최대 10 이하이기 때문에 LookUp Table을 구성해서 DP[] 값을 출력한다. DP[1..10] DP[1] DP[2] DP[3] DP[4] 1 → "1" 1 + 1 → "1" 2 → "1" 1 + 1 + 1 → "1" 1 + 2 → "2" 3 → "1" 1 + 1 + 2 → "3" 1 + 3 .. 2021. 8. 9.
[BOJ] 백준 1024 수열의 합 출처: https://www.acmicpc.net/problem/1024 Approach L 길이를 가지는 (x, x+L]에 대해 수식을 세우면. N = (x + 1) + ... + (x + L) 이다. → N = Lx + L * (L + 1) / 2 → N - (L * (L + 1) / 2) = Lx (좌항) N - (L * (L + 1) / 2) 이 L로 나누어 떨어지면 x를 구할 수 있다. 정달 출력시에는 x + 1 부터 x + L 까지 출력한다. C++ #include int main() { // freopen("input.txt", "r", stdin); int N, L; scanf("%d %d", &N, &L); for (int l = L; l = 0) { for (int len = 0; le.. 2021. 8. 7.
[BOJ] 백준 1110 더하기 사이클 출처: https://www.acmicpc.net/problem/1110 Approach 0 과 99 사이의 정수가 주어진다. 일의 자리수가 주어지더라도 앞쪽에 '0'을 붙여서 두 자리 취급을 한다. ex) 8 → 08 결과적으로 두 자리수가 주어지는 것으로 볼 수 있다. ① 10으로 나누었을 때, 왼쪽 자리 숫자가 무엇인지 알 수 있다. → L ② 오른쪽 자리 숫자는 나머지 연산(%)으로 구할 수 있다. → R ③ 새로운 숫자에서 가장 오른쪽 숫자는 → (L + R) % 10 = nR ④ 새로운 숫자는 → (R * 10) + nR 이다. 이 과정을 반복하면서 제일 처음 입력받은 숫자가 몇 회(cycle)만에 나오는지 확인한다. C++ #include int L, R, nR, num, cycle, old.. 2021. 8. 6.
[BOJ] 백준 1977 완전제곱수 출처: https://www.acmicpc.net/problem/1977 Approach 완전탐색 기법이란? 유형 문제이다. 완전탐색 기법이란? 가능한 모든 값을 대입해보는 무식한(?) 방법에 해당된다. 문제 내용 속에서 특정 규칙을 찾아서 모든 Case를 대입해보지 않고도 풀리는 경우도 있지만 충분한 제한 공간과 시간이 주어진다면 zoosso.tistory.com 두 수 N, M이 10000 이하의 자연수이기 때문에 M, N 사이의 특정 구간을 모두 탐색해도 TLE가 발생하지 않는다. for문으로 탐색하되, 완전 제곱수를 i * i로 표현 - M과 N사이의 숫자인지 - 해당 되는 완전 제곱수들의 합 - 최소값 처리 #include const int MAX_NM = 1e4; inline int min(i.. 2021. 8. 5.
[BOJ] 백준 1934 최소공배수 출처: https://www.acmicpc.net/problem/1934 Approach 두 수가 주어지면 최소공배수(Least Common Multiple, LCM)를 구하는 문제이다. 문제에서 설명한대로 최소 공백수의 정의를 이용해서 반복문으로 단순하게 구현할 수도 있지만 최대 공약수(Greatest Common Divisor, GCD)는 유클리드 호제법(Euclidean Algorithm)을 이용하여 구할 수 있다. 또한 최대 공약수를 통해서 최소공백수(LCM)를 쉽게 구할 수 있다. → LCM = A * B / GCD(A, B) ex) 10과 50의 최소공배수 = 50 일 때, 10과 50의 최대공약수 = 10 → 최소공배수 (LCM) = 50 = 10 * 50 / 10 정답 출력시에는 별도 배열.. 2021. 8. 4.
[BOJ] 백준 13701 중복 제거 출처: https://www.acmicpc.net/problem/13701 Approach 메모리 제한이 8MB (= 8,000,000 Byte)로 여유롭지 못한 편이다. 중복되는 숫자인지 확인하는 방법 중에는 int arr[n];에서 n이 기존에 등장한 숫자인지 확인하는 것이다. 하지만 n의 범위가 33554432로 1 Byte인 char 타입으로 구현해도 → 33,554,432 → 대략 34 MB 크기가 필요하다. ▶ [ps] 알고리즘 문제 풀 때, 메모리 제한? (feat. 구조체 메모리 계산) [ps] 알고리즘 문제 풀 때, 메모리 제한? (feat. 구조체 메모리 계산) 코딩 테스트와 같이 알고리즘 문제 풀 때, 메모리 제한이 엄격한 경우가 있다. 이때는 문제 설계 단계에서 메모리가 얼마나 필요.. 2021. 8. 2.
[BOJ] 백준 2210 숫자판 점프 출처: https://www.acmicpc.net/problem/2210 Approach 모든 Case를 비교해야 하므로 완전탐색 유형에 속한다. 완전탐색 기법이란? 가능한 모든 값을 대입해보는 무식한(?) 방법에 해당된다. 문제 내용 속에서 특정 규칙을 찾아서 모든 Case를 대입해보지 않고도 풀리는 경우도 있지만 충분한 제한 공간과 시간이 주어진다면 zoosso.tistory.com 5 * 5 칸에 인접한 4가지 방향으로 이동가능하므로 52 × 45 = 25600 에 해당한다. 또한 전형적인 DFS 유형 문제이기도 하다 깊이 우선 탐색(depth-first search, DFS) DFS 그래프의 모든 정점을 방문할 때 최대한 깊숙히 정점을 방문하는 방식입니다. - Stack 이용 즉, 연결된 정점을 .. 2021. 7. 29.
[BOJ] 백준 2309 일곱 난쟁이 출처: https://www.acmicpc.net/problem/2309 Approach 완전탐색 유형 문제이다. 완전탐색 기법이란? 가능한 모든 값을 대입해보는 무식한(?) 방법에 해당된다. 문제 내용 속에서 특정 규칙을 찾아서 모든 Case를 대입해보지 않고도 풀리는 경우도 있지만 충분한 제한 공간과 시간이 주어진다면 zoosso.tistory.com - 9명의 난쟁이 중에서 7명 선택해서 그 숫자의 합 = 100 이면 된다. - 출력 시, 오름차순으로 해야 하기에 선택 전/후로 오름차순 정렬시켜준다. ▶ 순열과 조합 순열과 조합 (백준 N과 M 시리즈) 순열과 조합 순열(Permutation) / 조합(Combination)에서 개수를 구하는 경우에는 ▶ P(n, r) = n × (n - 1) × .. 2021. 7. 28.
[BOJ] 백준 2231 분해합 출처: https://www.acmicpc.net/problem/2231 Approach 완전탐색 유형 문제이다. 완전탐색 기법이란? 가능한 모든 값을 대입해보는 무식한(?) 방법에 해당된다. 문제 내용 속에서 특정 규칙을 찾아서 모든 Case를 대입해보지 않고도 풀리는 경우도 있지만 충분한 제한 공간과 시간이 주어진다면 zoosso.tistory.com 자연수 N이 주어졌을 때, 가장 작은 생성자를 구해야 한다. → X가 생성자 일 때, X + (X의 요소들 각각을 더한 수) = N ex) 156 + 1 + 5 + 6 = 168 (=N) 수학적 특성을 찾아내서 탐색 범위를 줄일 수도 있겠지만 N의 범위가 크지 않기 때문에 1 ~ N 까지 모든 Case를 시도해보면 된다. 생성자 X의 구성하는 숫자를 하.. 2021. 7. 27.
[BOJ] 백준 3085 사탕 게임 출처: https://www.acmicpc.net/problem/3085 Approach 완전탐색 유형 문제이다. 완전탐색 기법이란? 가능한 모든 값을 대입해보는 무식한(?) 방법에 해당된다. 문제 내용 속에서 특정 규칙을 찾아서 모든 Case를 대입해보지 않고도 풀리는 경우도 있지만 충분한 제한 공간과 시간이 주어진다면 zoosso.tistory.com 인접한 2 칸을 선택하고 위치를 서로 교환한다. (대각선은 인접하지 않으며 세로/가로 방향으로 인접한 것으로 정의) - 최대 N이 크지 않은 수치이기 때문에 (3 ≤ N ≤ 50) 세로 방향과 가로 방향으로 구분해서 변경할 수 있는 위치를 모두 바꿔(swap)본다. - 바꿔볼 때마다 먹을 수 있는 사탕 개수를 확인하다. - 최대로 먹을 수 있는 사탕 개.. 2021. 7. 24.
반응형

티스토리툴바