오답노트

https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net - 문제 파악 정수 N과 정수 P1~Pn이 주어진다. P1~ Pn를 적절히 조합하여 N을 만드는 경우의 수중에서 Pi 요소의 합이 최소값을 출력하라. -정답 https://dhjkl123.tistory.com/54 [DP] BOJ 11052 카드 구매하기 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net - 문제 파악 정수 N 과 P1~PN 의 정수가 주어진다. 1~N 을 적절히 조합하여 N을 만드는 수의 조합에서 Pi들의 합이 최대값을 출력하라. -정답 1. 경우의 수 모든 경우의 수를 살펴 보지 않고 D[i-1] + D[1]만 확인했었다. 점화식을 찾는 도중 D[i-1] + D[1] = D[i-2] + D[2] 를 찾았고, 시간 초과를 염려해서 2중for문을 기피하려고 했다. 하지만 위 점화식은 여러..

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net - 문제 파악 정수 N 이 주어지고 1x2 , 2x1 , 2x2 타일로 N을 채우는 경우의 수 출력 - 나의 접근 조합 알고리즘으로 접근해서 예제는 맞았지만 1000이 틀렸다. 이전에 11726번을 풀다가 틀렸음에도 뭔 자신감인지 복습 안하고 풀었다가 당했다. 그때랑 비슷하게 당한거 같은데.. 앞으로는 이렇게 풀자.. 다이나믹 프로그래밍(DP)은 점화식이다.. -정답 #include "bits/stdc++.h" using na..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net - 문제 파악 정수 두개와 첫번째 정수 크기만큼의 수열을 입력한다. 입력된 수열을 조합하여 만든 수열의 합이 두번째 수열이 되는 경우의 수를 출력하라. 중복은 없다. - 나의 풀이 백트래킹으로 풀면 된다고 생각했으나, 중복문제 그리고 시간 초과로 인해서 제대로된 결과를 얻을 수 없었다. 아래 정답은 재귀를 활용한 코드인데, 아이디어가 괜찮은것 같다. 일반적인 백..

https://www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net - 문제 파악 공집합 S가 있고 문자열과 정수가 입력되면 그에 맞는 기능을 실행하고 check가 입력되면 같이 입력된 정수의 상태를 출력한다. - 정답 비트마스크 문제이지만 배열로 풀었다. #include "bits/stdc++.h" using namespace std; int arr[22]; int ans = 0x7ffffff; int main() { cin.tie(NULL); ios::sync_with_stdio(false); ..

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net - 문제 파악 정수 N 과 NxN의 2차원 배열이 주어진다. i->j 에서 가는 비용은 2차원의 배열에서 [i][j]의 원소값과 같다. 0부터 N-1 까지 순회하는데 비용의 최소값을 출력하라. - 정답 N-1 에서 0으로 돌아오는 것도 계산해야한다. #include "bits/stdc++.h" using namespace std; int arr[11][..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net - 문제 파악 정수 N이 주어지고 N개의 수열이 주어진다. 이 수열을 적절히 조합하여 아래 식으로 계산 하였을때 최대값을 출력하라. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| -정답 아래 식을 대충봐서 처음에 이해가 안됐지만 자세히 보니 N-2 까지 자기 자신과 다음 수열과의 차에 대한 절대값을 계속 더하는 공식이다. 사전순으로 찾아가기 위해 받은 수열을..

https://www.acmicpc.net/problem/10973 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net - 문제 파악 주어진 순열의 사전순으로 이전 순열을 출력, 출력할 수 없을 때는 -1을 출력한다. https://dhjkl123.tistory.com/46 STL 순열 관련 함수 ( next_permutation, prev_permutation, rotate) - next_permutation 오름차순 정렬된 컨테이너를 받는다 입력 컨테이너의 다음 순열을 입력 컨테이너에 입력한다. 다음 순열이 존재하면 true, 존재하지 않으면 false #includ..

https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net - 문제 파악 주어진 순열의 다음 순열을 출력한다. 다음 순열이 없을 경우 -1 을 출력한다. - 나의 접근 재귀로 주어진 순열을 찾고 그 다음 순열을 찾도록 했으나, 채점률이 아예 오르지도 못한채 문제를 계속틀렸다. -정답 STL 함수중에 순열에 관련된 함수가 있었다. (진짜 왕짜증.. 이러면서 배우는거지..) https://dhjkl123.tistory.com/46 STL 순열 관련 함수 ( next_permutation, prev_permutation..

https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net - 문제 파악 부등호 문자열을 주고 부등호 사이에 각 부등호를 만족하는 수를 넣는다. 그 수를 합쳐서 한 개의 수를 만들 때 그 수의 최대값과 최소값을 출력하라. - 정답 재귀 함수 완전탐색 #include "bits/stdc++.h" using namespace std; int n; char szarr[10]; int narr[10]; string strmax; string strmin; string str..