답은 알고리즘 뿐이야!

문제 출처 : https://www.acmicpc.net/problem/1644 풀이 : 소수문제입니다. 소수는 항상 에라토스테네스의 체를 사용하시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include int n,arr[4000001],s[300000],cnt,ret,sum; int main() { scanf("%d", &n); for (int i = 2; i = 0&&sum

문제 출처 : https://www.acmicpc.net/problem/1932 풀이 : DP 문제입니다. 저는 위의 두개의 값을 비교하여 채워나가는 형식으로 짰습니다. 왼쪽과 오른쪽의 값중 큰것을 선택하여 그 셀에 합쳐 나가시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include #define max(A,B) ((A)>(B)?(A):(B)) int n, arr[500][500],ret,l,r; int main() { scanf("%d", &n); for (int i = 0; i

문제 출처 : https://www.acmicpc.net/problem/2644 풀이 : 두 사람 사이의 촌수를 계산하는 문제입니다. 이는 두 사람 사이에 엣지가 몇개 있는지를 묻는 문제로 지나간 엣지 갯수를 저장해주면서 탐색하시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include #include using namespace std; queueq; pair p; int n, s, e, map[101][101], check[101], a, b, k; int main() { scanf("%d\n%d %d\n%d", &n, &s, &e, &k); while (k--) { sc..

문제 출처 : https://www.acmicpc.net/problem/8902 풀이 : 2차원 DP문제입니다. 두개의 라인이 존재하는데 각라인에서 몇대가 합류했는지를 DP로 쌓으시면 됩니다. 저는 cache[line1][line2]의 형태로 저장했습니다. 문제에서 원하는 결과값은 결국 모든 끝나는 지점에서 모든 시작지점을 뺀 값과 같습니다 따라서 cache를 쌓을때 각 색깔별로 맨처음과 맨끝이 어디있는지를 비교하여 1. 그 색깔에서 맨 처음 나왔을 경우 : 그 위치를 (-) 해줌 2. 그 색깔에서 맨 마지막에 나왔을 경우 : 그 위치를 (+) 해줌 위의 두개지 규칙을 적용하여 풀었습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..

문제 출처 : https://www.acmicpc.net/problem/9095 풀이 : DP문제입니다. 1, 2, 3으로 새로운 방법을 만들 수 있는 경우는 i-1인 경우 : + '1' i-2인 경우 : + '2' i-3인 경우 : + '3' 이 세가지 경우 입니다. 따라서, cache[i] = cache[i-1]+cache[i-2]+cache[i-3]대로 쌓으면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include int t,n,cache[11]; int main() { scanf("%d", &t); cache[1] = 1, cache[2] = 2,cache[3] =4; for (int i = 4; i

문제 출처 : https://www.acmicpc.net/problem/17521 풀이 : 2019 ICPC 예선문제입니다. 모든 정보를 알기 때문에 최대의 이익을 뽑아내기 위해서는 항상 저점 매입해서 고점에서 매도하면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include int n, arr[16], ma, mi; long long int k; int main() { scanf("%d %lld", &n, &k); for (int i = 0; i

문제 출처 : https://www.acmicpc.net/problem/2343 풀이 : 이분 탐색 문제입니다. 블루레이의 길이를 기준으로 이분탐색을 돌아 가능한 모든 경우의수를 다 시도해봅니다. 이분 탐색을 돌 때 left와 right를 기준으로 도는데, 1. Mid 값이 문제조건을 만족 할 때, (즉, Mid값을 블루레이의 길이로 잡고 M을 채울때 M개 안에 다 채워 질 때) - binary( left , Mid - 1 ) 2. Mid 값이 문제 조건을 만족 시키지 못 할 때, - binary( Mid + 1, right ) 위와 같이 탐색하시면 됩니다. O(n) * O(logn) 으로 총 O(nlogn)의 시간복잡도를 가집니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ..

문제 출처 : https://www.acmicpc.net/problem/5430 풀이 : 큐 문제입니다. 이 문제는 배열을 자주 뒤집어야 하는데 말 그대로 뒤집기만 하면 타임오버가 납니다. front 와 rear의 위치만 바꿔 주어 O(1)로 뒤집은 듯한 효과를 내시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 #include struct reverse_queue { int data[100001]; int front, r..

문제 출처 : https://www.acmicpc.net/problem/11055 풀이 : DP문제 입니다. 가장 큰 값을 가지는 LIS가 아니라 가장 큰 값을 가지는 증가 부분 수열 이라는 점에 주의합시다. 값을 쌓아 가실 때 이전까지 증가 수열 중 현재 값과 증가 수열을 이루면서 가장 큰 값을 갖는 증가수열이 되도록 쌓아가시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include int n,arr[1000],cache[1000],max; int main() { scanf("%d", &n); for (int i = 0; i

문제 출처 : https://www.acmicpc.net/problem/16500 풀이 : DP문제입니다. 문자열을 처음부터 끝까지 훑으면서 단어들과 매칭합니다 그리고 단어 목록들로 문자열의 현재 시점까지 완성 시킬 수 있는지 없는지 여부를 word배열에 쌓아가는데, 쌓을 때 현재 검사하고있는 S문자열의 바로 앞 문자까지 완성되있는지 여부를 확인하고 완성되어 있으면 word 배열에 완성 됬다고 쌓아가시면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include char comp[101]; char carr[101][101]; int n,word[101]; int main() { scanf("%s", comp)..