프로그래밍/문제풀이(boj)
1. 문제링크https://www.acmicpc.net/problem/1766 2. 문제해설이 문제는 위상정렬 문제에 priority_queue를 사용하는 문제이다.1. 위상정렬을 한다.2. 하는 중에 queue를 priority_queue로 바꿔서 위상정렬을 한다. 3. 소스코드 #include #include #include #include #include using namespace std; #define fio ios_base::sync_with_stdio(0); cin.tie(0); #define MAX_NUM 32000 int main(){ fio int n, m; int idgr[MAX_NUM+1]={0}; vector v[MAX_NUM+1]; priority_queue q; cin >> n..
1. 문제링크https://www.acmicpc.net/problem/1005 2. 문제해설이 문제는 간단한 위상정렬 문제이다.1. 각 노드까지 오는데 걸리는 시간을 저장하는 배열을 만든다.2. 위상정렬을 하면서 축적하며 가장 큰 값들을 들고 온다.3. 원하는 노드에 왔을 때 그 노드를 만드는데 걸리는 시간을 더한 후 출력한다. 3. 소스코드 #include #include #include #include #include using namespace std; #define fio ios_base::sync_with_stdio(0); cin.tie(0); #define NODE 1000 void testcase(); struct node{ int e, w; }; int main(){ fio int t; c..
1. 문제링크https://www.acmicpc.net/problem/2229 2. 해설이 문제는 dp문제로, 연속되게 조를 짜는데, 조원들 중 가장 큰 점수와 가장 적은 점수의 차가 최대한 많이 나게 만드는 것이 목표인 문제이다. i부터 j까지 연속된 조들의 최대 값과 최소 값을 전부 저장한 후에 dp를 풀었다. dp 테이블은 "dp[i] = i번째 학생까지 조를 짤 때 최대로 얻을 수 있는 점수" 로 구현했다. 필자는 dp[i]를 구하기 위해서 0~i 돌면서 dp[index] 에 저장 되어 있는 값 + (index + 1) ~ i 의 최대 차이 를 구해서 저장하고 다녔다.정리하자면1. i ~ j 의 최대, 최소값을 구하고 저장한다.2. dp[i]를 구하기 위해 0~i 를 돌면서 최적을 찾는다. 시간복..
1. 문제링크https://www.acmicpc.net/problem/13398 2. 해설이 문제는 연속합 1과는 다르게 차원을 하나 더 설정해서 풀어줘야 한다.내가 지금까지 더한 값이 하나를 빼고 더한 것인가 아니면 빼지 않은 채로 더한 것인가를 따로 저장하면서 다녀야한다. 1. 처음 초기화를 한다.2. dp[0]은 빼지 않고 더한 값, dp[1]은 빼고 더한 값들 중 최적을 저장하고 다닌다.3. dp 배열 안에 가장 큰 값을 출력한다. 3. 소스코드 #include #include #define MAXNUM 100100 using namespace std; int arr[MAXNUM]={0}; int dp[2][MAXNUM]={0}; int main() { int n, ans= -1010; scanf..
1. 문제링크https://www.acmicpc.net/problem/10845 2. 해설이 문제는 간단하게 큐를 구현하는 문제이다. 3. 소스코드 #include using namespace std; class queue{ private: int q[10001]={0}; int head=0, tail=0; public: void push(int x){ q[tail++] = x; } void pop(){ head++; } int front(){ return q[head]; } int back(){ return q[tail-1]; } int size(){ return tail - head; } int empty(){ return (tail - head == 0) ? 1 : 0; } }; int main()..
1. 문제 링크https://www.acmicpc.net/problem/2096 2. 해설이 문제는 간단한 트릭을 사용하는 dp 문제이다. 평소에 dp 문제를 푸는 식으로 문제를 풀게 되면 14MB의 작은 메모리 공간에 메모리 초과라는 결과를 맞게 된다. 간단하게 메모리를 재사용하면 답을 구할 수 있다. 1. 첫 줄을 받고 int dp[3][3] 이라는 배열에 대입한다.2. 2번째 줄부터는 2차원 dp 배열의 0번째 줄의 값들 중 가능한 최대와 최소를 구해서 1번째 줄에 대입한다.3. 다시 1번째 줄을 0번째 줄에 대입하고 반복한다. 3. 소스코드 #include #include #include #define fio ios_base::sync_with_stdio(0), cin.tie(0) #define ..
1. 문제 링크https://www.acmicpc.net/problem/1526 2. 문제 해설이 문제는 4와 7로 이루어진 수 중에서 주어진 수 보다 작은 가장 큰 수를 찾는 문제이다. 여러 풀이가 있을 수 있지만 필자는 구해놓고, 찾는 방식을 택했다. 1. vector에 4와 7을 push_back 한다.2. 4에서 나올 수 있는 가지수인 44, 47을 push_back한다.3. vector 의 그 다음 수를 찾아서 다음으로 나올 수 있는 수를 push_back 한다.4. 주어진 n보다 커질 때 까지 반복한다.5. binary search를 사용해서 n보다 작으면서 가장 큰 수를 찾는다. 3. 소스코드 #include #include #include #include #include #include u..
1. 문제 링크https://www.acmicpc.net/problem/1525 2. 문제 해설이 문제는 얼핏 봐서는 간단한 BFS문제로 보인다. 하지만 실제로 단순한 BFS짜려면 문제가 하나씩 생긴다. 첫번째 문제는 일반적인 BFS와 다르게 움직일 때마다 필요한 상태가 전부 다르기 때문에 큐에 넣을 때 마다 상태를 같이 넣어주어야 한다.두번째 문제는 첫 번째 문제에서 생기는데, 그냥 상태를 전부 큐에 푸쉬 해서 문제를 내면 메모리 초과가 나온다. 왜냐하면 주어지는 메모리가 16MB밖에 주어지지 않기 때문이다. 평소에는 거의 128MB, 256MB를 잡아서 메모리를 넉넉하게 사용하였지만, 이번 문제는 그렇지 않다. 최대한 메모리를 적게 먹는 방법을 사용해서 풀어야한다. 우리는 총 가지수가 9! 개수 만큼..
1. 문제 링크https://www.acmicpc.net/problem/2225 2. 문제 해설이 문제는 전형적인 dp문제이다. dp 테이블을 어떻게 잡느냐가 제일 핵심인데, 필자는 x축을 n, y축을 k로 놓고 문제를 풀었다. 순서대로 풀이를 해보자면1. k가 1일 때는 모두가 자기 자신만 더하면 되는 것이므로 모두 개수가 1개이다.2. k가 2일 때는 자신보다 x 작다면 x를 더해주면 되는 것이므로 자신보다 작은 k가 1인 값들을 전부 더해주면 자신의 값이다.예를들어 n이 5라면(5 + 0), (4 + 1), (3 + 2), (2 + 3), (1 + 4), (0 + 5)이렇게 6개가 된다.3. k가 3일 때는 자신보다 앞에서 구해놓은 k가 2일 때의 값들을 자신보다 작거나 같은 n의 값들을 전부 더해..
