오답노트

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net - 문제 파악 NxN 배열에 임의 숫자들이 들어가 있고, 0부터 N-1 중에서 N/2 개의 숫자를 임의로 택한 숫자들의 원소의 합과 나머지 숫자들의 원소의 합의 차가 제일 작은 수를 출력한다. - 나의 접근 재귀로 접근하는 것은 좋았으나, 좀 더 경우의 수를 줄이려는 법을 찾다가 코드가 더 복잡해져버렸다. 직관적으로 접근해도 괜찮았을것 같다. (지금까지 경험으로 직관적으로 했을때 시간초과가 날지 안날지 판단하는게 제일..

https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net - 문제 파악 임의의 숫자 N이 주어이고 그 수를 1부터 N까지 이어 붙혀 새로운 수를 만들 수 있다. 이 새로운 수의 자리수를 구하여라 - 정답 1. N 의 자리수를 nSize라고 할때, nSize -1 자리수까지는 1부터 10^nSize -2 이므로 모두 더한다. 2. 나머지 10^nSzie-1 부터 N까지는 nSize 자리수 가 N - 10^nSize -1 개 만큼 있으므로 nSize * (N - 10^nSize - 1)을 1번과 더한다. #include "bits/stdc++.h" using namespace ..

https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net - 문제 파악 15진수 28진수 19진수로 주어진 수로 원래 숫자를 알아낸다. - 실수 시간 초과로 헤멨는데, 각각 15, 28, 19 중 하나라도 해당되면 if 문으로 들어가지 못해 무한루프를 돌았다. 예외 처리하니 바로 통과 - 정답 #include "bits/stdc++.h" using namespace std; int ans; int main() { cin.tie(NULL); ios::sync_..

https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net - 문제 접근 4종류의 사탕이 NxN의 배열에 존재할 때,인접한 한 쌍의 사탕을 바꿔서 상하 또는 좌우로 가장 긴 사탕의 개수를 구한다. 0. 초기값에서 중복되는 사탕의 개수 중 최대값 저장 1. bfs와 같은 원리로 인접한 사탕이 다른 위치를 큐로 저장 2. 큐를 돌면서 상하좌우에 자신과 다른 사탕이 있으면 바꿈 3. 바꾼 열과 행을 확인하여 중복되는 사탕의 개수 확인 4. 3에서 얻은 값의 최대값과 0번의 최대값 비교 5. 1~4 반복해서 최대값을 출력 - 정답 (중복되는 코드는 함수로 만들자) #include..

https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net - 문제 파악 9명의 난쟁이들 키중에서 7명의 키의 합이 100임을 이용한다. - 나의 시도 9명의 모든 경우의 수를 살피면서 100 - (경우의 수 합) = 0 임을 이용하려고 했으나 너무 복잡하게 접근 - 정답 9명 모두의 합중에서 2명의 키만 빼면 100이 됨을 이용, 나의 시도와 비슷하지만 nCk = nCn-k 임을 이용해서 문제를 더 간단하게 만들었다. #include "bits/stdc++.h"..

https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net - 문제 파악 입력된 숫자들 중 소수의 개수를 출력한다. - 정답 #include "bits/stdc++.h" using namespace std; int main() { int t; cin >> t; int ans = 0; while (t--) { int n; cin >> n; if (n == 1) continue; bool flag = false; for (int i = 2; i

https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net - 문제 파악 2부터 입력에서 주어진 수만큼 배수를 지운다. 지운 배수들은 배열에 넣어놓고 반복문에서 이미 지운 배수를 조회할 땐 지나친다. - 정답 코드 #include "bits/stdc++.h" using namespace std; int arr[1005]; int main() { int n, k; cin >> n >> k; int ans = 0; for (int i = 2; i n) break; if (arr[a]) continue; arr[a]++; ans++; if (ans..

https://www.acmicpc.net/problem/17425 17425번: 약수의 합 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net - 문제 파악 약수의 합2 와 같은 문제라고 생각하고 풀이 시작, 하지만 Test Case 만큼 더 약수 계산을 수행해야한다. - 나의 시도 1. 일단 무식하게 약수의 합2를 Test Case 수행 -> 시간초과 2. 배열에 미리 만들어 놓고 그것을 주어진 수에 대해서 빼야겠다고 생각 -> 하지만 배열에 어떤식으로 넣을지, 또 어떤식으로 출력..

https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net - 문제 파악 자연수 N이 주어지면 1부터 N까지 각 자연수 마다 약수의 합을 모두 더하는 문제 - 나의 시도 무식하게 1부터 약수 구하여 더하고 를 N까지 반복, 하지만 자료형은 신경써서 unsigned long long 으로 답을 도출 하였으나.. 결과는 시간 초과 log(N) 이 되도록 로직을 구성하려고 시도했다. 자연수 k의 배수는..

내가 지금까지 DP 문제를 풀면서 어느정도 패턴이 있다고 생각하여, 그 패턴을 정리 해보려고 한다. 하지만 무조건 여기에 정리한 패턴이 나오는건 아니다. 그래도 한 번 정리하고 넘어가면 다음에 비슷한 문제는 해결할 수 있을것 같다. - 현재까지 계산된 값을 넣어놓는 패턴 1. n개의 배열 (arr[n])이 주어지면 arr[0]부터 arr[i]까지의 무언가 연산한 결과를 D[i]에 넣는다. 2. 이때 기준이 있어야 하므로 2중 for문을 사용한다. 3. D[i]는 D[j]와 arr[i]를 연산하는 것 생각해본다. 4. 내가 가장 많이 하는 실수는 요소의 기준을 항상 요소의 처음부터라고 생각한다. 요소의 끝을 먼저 정하고 풀이를 생각해보자. - 선택지를 주고 이 중에서 하나를 선택하는 패턴 1. D[i]는 ..