1450번: 냅색문제 (acmicpc.net) 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net Meet in the middle 알고리즘을 배우는 문제로 투포인터를 응용한 개념을 이용하여 문제를 해결하였다. 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 ..

1806번: 부분합 (acmicpc.net) 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 투포인터 문제로 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 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 #include #include #define NON 1000000 usi..

2470번: 두 용액 (acmicpc.net) 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net set에 원소들을 넣어서 정렬하고 투 포인터를 이용해서 문제를 해결했다. 아마도 시간을 줄이는 방법으로는 set을 이용하지않고 모든 원소를 vector에 저장하고 한번에 정렬하면 더 빠른 풀이로 해결 가능하다. 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 3..

https://www.acmicpc.net/problem/9660 9660번: 돌 게임 6 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www.acmicpc.net 입력값이 매우 크기때문에 DP로 할 경우에는 시간이 오래걸리므로 돌 게임의 규칙을 찾아서 해결하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); long long N; cin >> N; if (N % 7 == 0 || N % 7 == 2) cout

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 가장 처음에 문제를 접했을때 도저히 아이디어가 생각이 나지 않아서 해결하지 못하고 넘어갔었다. 이것보다 난이도가 낮은 문제인 같은 이름의 문제인 트리의 지름에서는 루트노드가 주어져서 문제를 해결했는데 다른 사람들의 풀이과정을 확인하니 트리의 지름을 찾는 특징이 있었다. !! 아무 정점에서 가장 먼 정점을 찾으면 트리의 지름을 연결하는 정점 2개중 한개라는 사실이다. 이러한 특징만 ..

16236번: 아기 상어 (acmicpc.net) 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 아기상어의 크기가 9초과이면 시간초과가 발생했는데 자기 자신이 9이기때문에 자시 자신을 먹어서 무한루프가 발생했다. 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..