[ 문제 ] 2003번 문제보기 N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. [ 제출코드 ] [ 풀이 ] 처음부터 더해서 sum이 M을 초과하면 sum=0으로 하고 i+1부터 다시 더한다. [ 이야기 ] '알고리즘 분류'를 보지 않고 풀었다.

[ 문제 ] 1920번 문제보기 [ 제출코드 ] [ 풀이 ] A = 4 1 5 2 3 B = 1 3 7 9 5 1. A배열을 오름차순으로 정렬. A = 1 2 3 4 5 2. left = 0번 인덱스, right = (n-1)번 인덱스, mid = ((left+right)/2)번 인덱스 1 2 3 4 5 left mid right if (A[mid] B[i]) right = mid-1; else 1출력; [ 참고 ] 이분탐색

[ 문제 ] 2309번 문제 보기 [ 제출코드 ] [ 풀이 ] 1. 모든 난쟁이의 키를 더해준다. 2. sumDiffer = (모든 난쟁이의 키) - 100 3. 배열을 오름차순으로 정렬한다. 4. 두 개씩 더해서 sumDiffer인 두 명을 선택한 뒤, 두 명의 키를 -1로 설정한다. 5. 0이상인 난쟁이의 키만 찾아서 출력한다. for i=0 to 8 for j=1 to 9 if (arr[i] + arr[j] == sumDiffer) { arr[i] = -1; arr[j] = -1; break; } [ 이야기 ] 내가 처음에 생각한 풀이는 다음과 같았다. 1. 배열을 오름차순으로 정렬한다. 2. 7개의 키를 더한다. 2-1. 키의 합이 100이 아니라면 가장 마지막을 pop하고 그다음 인덱스를 pus..

[문제] 1026번 문제보기 [제출코드] #include #include #include int main(){ int N; std::cin>> N; std::vector A; std::vector B; for(int i=0; i> x; A.push_back(x); } for(int i=0; i> x; B.push_back(x); } std::vector tempA(N, 0), tempB(N, 0); std::copy(A.begin(), A.end(), tempA.begin()); std::copy(B.begin(), B.end(), tempB.begin()); std::sort(tempB.begin(), tempB.end()); std::sort(tempA.begin(), tempA.end()); std..

[문제] 1463번 문제보기 [제출코드] [풀이] 1 2 -> 1 3 -> 1 4 -> 3 -> 1 5 -> 4 -> 3 -> 1 6 -> 2 -> 1 ... 노란색으로 칠해진 부분은 이미 앞에서 연산된 부분이다. 했던 계산을 또 하는 것은 비효율적이므로, 연산을 사용하는 최솟값을 배열에 저장한다. [이야기] 항상 vector만 사용했기에 이번에는 동적배열을 사용해보고 싶었다. [참고] 함수로_배열_전달

[문제] 10870번 문제보기 [제출코드] [이야기] 이 문제는 다이나믹 프로그래밍을 안다면 너무 쉽게 풀 수 있는 문제다.

[문제] 1003번 문제보기 [제출코드] [풀이] f(0) = 0 f(1) = 1 f(2) = f(1) + f(0) = 1 + 0 f(3) = f(2) + f(1) = { f(1) + f(0) } + f(1) = 1 + 0 + 1 ... 재귀로 풀면 위처럼 이미 계산한걸 또다시 계산해야하므로 비효율적이다. 하지만 DP로 풀게 되면, f(0)과 f(1)의 결과만 배열에 저장해놓고 2이상의 n은 앞의 2개의 결과를 더해주기만 하면 되므로 훨씬 시간이 단축된다. [이야기] 알고리즘을 배우기 전 DP를 몰라서 시간초과로 틀렸던 문제다. 그때는 다이나믹을 생각하지 않고 재귀로 해서 틀렸었다.

[문제] 16953번 문제보기 [제출코드] [풀이] 1. B에서 일의 자리가 1인지 확인 1-1. 1이면 B = B%10; 1-2. 1이 아니면 B를 2로 나눠줌. 1-3. B가 일의 자리가 1이 아닌 홀수인 경우 A로 B를 만들 수 없으므로(2를 곱하므로) -1 리턴. 2. 위의 경우를 수행했는데 A보다 B가 작아지면 A로 B를 만들 수 없다는 의미이므로 -1 리턴. [이야기] 한 번에 "맞았습니다!"를 보고 싶어서 여러 반례로 테스트를 했다. 1 3 인 경우 결과가 2로 나와 1-3을 추가해주었다. 그 결과 한 번에 "맞았습니다!"를 볼 수 있었다!

5585번 문제보기 제출코드 #include #include #include #include int main(){ int answer = 0, price; // 동전 종류 std::vector money; money.push_back(500); money.push_back(100); money.push_back(50); money.push_back(10); money.push_back(5); money.push_back(1); std::cin >> price; int change = 1000-price; for(int i=0; i < money.size(); i++){ if(change < 0) break; if(money[i]

11047번 문제보기 제출코드 #include #include #include #include int main(){ int answer = 0, n, k; std::cin >> n >> k; std::vector money; // 동전의 종류 for (int i = 0; i > kind; money.push_back(kind); } for(int i=money.size()-1; i >= 0; i--){ if(k