본문 바로가기

BOJ22

BOJ 2104 부분배열 고르기 문제링크 : https://www.acmicpc.net/problem/2104 2104번: 부분배열 고르기 크기가 N(1 ≤ N ≤ 100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1 ≤ i ≤ j ≤ N)에 대한 점수는, (A[i] + … + A[j]) × min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에 i부터 j까지의 최솟값을 곱 www.acmicpc.net 요약 크기가 N의 1차워 배열의 부분배열의 합과 부분배열에서의 최솟값의 곱의 최대값을 구하는 문제 풀이 완전 탐색으로 해결하기에는 시간초과가 우려된다. 분할정복을 통해 해결해보았다. 두 부분으로 나눠서 왼쪽에서 가장 큰 점수를 갖는 부분 배열과 오른쪽에서 가장 큰 점수를 갖는 부분배열을 비교해준.. 2022. 3. 12.
BOJ 1629 곱셈 문제링크 : https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 요약 (A^B)%C를 구하는 문제 풀이 주어지는 세 수의 최댓값이 2,147,483,647이다. 지수값이 저렇게 큰수면 곱하다가 시간초과 나버린다. 시간복잡도를 줄이기 위해서 분할정복으로 해결하여야 한다. 지수 B가 짝수인 경우에는 A^B=(A^(B/2))^2 이고 홀수인 경우엔 A^B = A*(A^((B-1)/2))^2이다. 이렇게 연산을 logB개로 줄일수 있게 되고 시간복잡도도 즉 O(logB)가 된다. 숫자가 매우 크기 때문에 long lon.. 2022. 3. 12.
BOJ 11047 동전 0 문제 링크 : https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 요약 N 개의 종류의 동전이 있고 각 동전은 무수히 많다. 동전을 조합해서 가치의 합을 K로 만들려고 할 때 필요한 동전의 최소 개수를 구하는 문제이다. 풀이 첫 번째 예제 입력값을 보자 1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000의 가치를 가진 동전들로 4200원을 만들어야 .. 2022. 3. 10.
BOJ 15748 Rest Stops 문제 링크 : https://www.acmicpc.net/problem/15748 15748번: Rest Stops The first line of input contains four integers: $L$, $N$, $r_F$, and $r_B$. The next $N$ lines describe the rest stops. For each $i$ between $1$ and $N$, the $i+1$-st line contains two integers $x_i$ and $c_i$, describing the position of the $i$-th rest st www.acmicpc.net 요약 으.. 영어 문제 간단하게 해석해보자면 Farmer John과 Bessie가 등산을 한다, Jhon과 .. 2022. 3. 10.

티스토리툴바