목록전체 글 (405)
오답노트
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/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net - 문제 풀이 에라토스테네스의 체로 미리 홀수 소수를 구하고 입력이 들어올 때 마다 n - (홀수 소수) 를 계산하여 결과가 홀수 소수인 값을 출력한다. - 문제 풀이시 중요한 것 문제 풀이는 맞았으나 cin 함수의 사용때문에 코드 자체가 느려서 시간초과가 발생했다. cin.tie(NULL); ios::sync_with_stdio(false); 위 두 코드는 cin 의 시간..
https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net - 문제 파악 주어진 두 개의 수 사이의 소수를 출력한다 ( 주어진 두 수 포함) - 정답 #include "bits/stdc++.h" using namespace std; int arr[1000005]; int main() { int n, m; cin >> n >> m; for (int i = 2; i 0) continue; for (int j = 2; i * j = n && i
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. 배열에 미리 만들어 놓고 그것을 주어진 수에 대해서 빼야겠다고 생각 -> 하지만 배열에 어떤식으로 넣을지, 또 어떤식으로 출력..