기술 블로그

https://www.acmicpc.net/problem/3067 냅색 #include using namespace std; int N, T, cache[10001][21]; vector v; int ks(int goal, int idx) { if (idx == N) { if (goal == 0) return 1; return 0; } int& ret = cache[goal][idx]; if (ret != -1) return ret; ret = ks(goal, idx + 1); if (goal - v[idx] >= 0) { ret += max(ks(goal - v[idx], idx), ks(goal - v[idx], idx + 1)); } return ret; } int main() { //freopen..

https://www.acmicpc.net/problem/14728 냅색 문제이다. #include using namespace std; int N, T, cache[10001][101]; vector v; int ks(int T, int idx) { if (idx == N) { return 0; } int& ret = cache[T][idx]; if (ret != -1) return ret; ret = 0; // 우선 현재 순서를 건너 뛰어본다. ret = max(ret, ks(T, idx + 1)); // 알맞은 조건 하에 현재 순서를 진행한다. if (T - v[idx].first >= 0) { // 비교 ret = max(ret, ks(T - v[idx].first, idx + 1) + v[idx..

수학, 자료구조, multimap https://www.acmicpc.net/problem/9375 각 Type에 Name을 담는다. 이때, 숫자가 아닌 문자열이고, 1개 초과로 담아야 하므로, multimap을 이용한다. 정답은 (각 Type에 속해 있는 Name의 개수 + 1)을 Type 수에 맞게 연산한다. #include using namespace std; int T, n; multimap mm; set st; int main() { //freopen("C:\\Users\\park7\\Desktop\\lazy_bronze\\2.in", "r", stdin); cin.tie(0); scanf("%d", &T); while (T--) { cin >> n; st.clear(); mm.clear(); ..

https://www.acmicpc.net/problem/2467 이분탐색 문제다. 참고로 두 용액의 합이 0이 될 수도 있다. 1. 맨 처음 원소와 맨 마지막 원소의 비교를 처음으로 설정한다. L = 0, R = v.size() - 1 2. 비교할 값(pivot)을 설정해, 각각의 절댓값을 비교하여 pivot을 갱신한다. 절댓값을 활용하는 이유는 -와 +를 고려할 필요가 없이 무조건 둘 중 작은 값이 0에 가깝기 때문이다. 3. L과 R은 v의 인덱스이고, (v[L] + v[R])이 0을 기준으로 큰지, 작은지, 같은지 비교한다. 4. 3의 결과에 따라, L과 R을 적절히 연산한다. 처음에 틀렸었는데 Update 함수 내의 if 조건문에서 pivot > abs(sum)로 작성했었다. pivot > ab..

유형 : 구현, 시뮬레이션, MST, BFS, DFS, 백트래킹, 브루트포스 18430번 무기공학 https://www.acmicpc.net/problem/18430 9935번 문자열 폭발 https://www.acmicpc.net/problem/9935 11559번 Puyo Puyo https://www.acmicpc.net/problem/11559 4991번 로봇 청소기 https://www.acmicpc.net/problem/4991 16932번 모양 만들기 https://www.acmicpc.net/problem/16932 16985번 Maaaaaaaaaze https://www.acmicpc.net/problem/16985 16987번 계란으로 계란치기 https://www.acmicpc.net..

www.acmicpc.net/problem/6987 6987번: 월드컵 www.acmicpc.net 예제 1에서 2번째 경우 계속 1이 아니라 0이 나와서 코드를 봤더니 bool chk = true;를 엉뚱한 곳에서 선언했었다. 이때문에 chk가 한 번이라도 false가 되버리면 그 후 계속 false가 되버리는 논리적인 오류가 있었다. 그래서 위치만 고쳤더니 예제 1도 맞고, 정답이었다. score[1 ~ 6][1 ~ 3] 1. (왼쪽 인덱스) A를 1로, B는 2로, ..., F는 6으로 생각하자. 2. (오른쪽 인덱스) 1은 승리, 2는 무승부, 3은 패배 #include using namespace std; int n, m; bool use[10]; int arr[10][20], score[10]..

www.acmicpc.net/problem/13908 13908번: 비밀번호 첫 번째 예제의 경우 가능한 비밀번호의 조합은 07, 17, 27, 37, 47, 57, 67, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 87, 97이다. 두 번째 예제의 경우 가능한 비밀번호의 조합은 34, 43이다. www.acmicpc.net 첫 번째 코드 : 백트래킹 - 추천 두 번째 코드 : int 숫자를 string 변환하면서, for문으로 모든 경우 다 탐색(개수를 셈하여 활용하는 방식) - 비추천 첫 번째 코드의 속도가 두 번째 코드의 속도보다 더 빠르다. #include using namespace std; int n, m, answer, a[10]; vector v; void bt..

www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net use 2차원 배열이 true일 때는 가로, false일 때는 세로로 생각하여 계산한다. #include using namespace std; #define MAX 5 int R, C, answer = INT32_MIN; int p[MAX][MAX]; bool use[MAX][MAX], tmp[MAX][MAX]; int calc(vector &v) { string str = ""; for (auto i : v..