풀이 A,B 각각의 단계에서 저장될 수 있는 최솟값을 dp로 구성하여 문제풀이를 하였다. 다른 라인으로 이동하지 않고 같은 라인의 다음 단계 시간과 이전 단계에서 다른 라인의 최솟값과 이동시간을 더한 값을 비교하여 점화식을 구성하였다. #include #include #include using namespace std; int main(int argc, char** argv) { int N; cin >> N; vector A(N), B(N), tA(N-1), tB(N-1); for (int i = 0; i > A[i] >> B[i] >> tA[i] >> tB[i]; } cin >> A[N - 1] >> B[N - 1]; vector dpA(N), dpB(N); dpA..

풀이 처음에는 dfs문제인줄 알았지만 풀다보니 일반 구현문제였다. 먼저 연관성을 입력 받고 반복문을 돌려 각 사람들에 연결된 사람들의 무게를 비교하며, 현재 단계 사람의 무게보다 연결된 사람의 무게가 더 무거우면 flag를 설정하여 카운트하지 않았다. #include #include using namespace std; int N,M; int W[100001]; vector vec[100001]; bool flag; int main(int argc, char** argv) { int u,v,ans=0; cin>>N>>M; for(int i=1;i>W[i]; } for(int i=0;i>u>>v; vec[u].push_back(v); vec[v].push_back(u); } for(int i=1;i

풀이 핵심은 끝나는 시간을 기준으로 정렬하는 것이었다. 이후 반복문을 돌며 각 강의의 시작하는 시간과 마지막 끝난 시간을 비교하여 후자가 더 작을 때 마지막 끝난 시간을 업데이트해주며, 강의 수를 카운트 해주었다. #include #include #include using namespace std; int N; int main(int argc, char** argv) { cin >> N; vector vec(N); for(int i = 0; i > vec[i].second >> vec[i].first; } sort(vec.begin(), vec.end()); int cnt = 0; int lastEndTime = 0; for(int i=0;i=lastEndTime){ las..

풀이 분할정복을 활용한 문제였다. 재귀를 통해 제곱수를 구해주어야 하는데 문제 부분에서 0.1초당 P가 곱해지기 때문에 N에 10을 곱한 값을 인자로 넘겨주어야 한다. 이후 1승은 P를 리턴해주는 베이스를 만들고, 제곱수를 분할한다. 짝수승의 경우 반환받은 제곱수를 곱해주면 되지만, 홀수승의 경우에는 P를 곱해주어 값을 구해주고 반환해줘야 한다. #include using namespace std; long long K,P,N; long long f(long long cur){ if(cur==1) return P; long long result = f(cur/2); result = result * result % 1000000007; if(cur%2==1) result = result * P % 1000..

풀이 배열 내에서 연속으로 증가하는 개수의 최댓값을 구하는 문제였다. 먼저 dp 배열 내 모든 원소에 1을 저장시켜준 후 2중 for문을 통해 dp를 진행시켰다. 사용된 점화식은 다음과 같다. dp[i] = max(dp[i],dp[j]+1) i보다 작은 인덱스들에 한해서 현재 i레벨에서 저장된 값보다 작은 값이 있으면, 이전 레벨에서의 dp값에 1을 더하며 최댓값을 구하였다. #include #include using namespace std; int N,dp[3001]; int main(int argc, char** argv) { int ans=0; cin>>N; fill(dp,dp+N,1); vector v(N); for(int i=0;i>v[i]; } for(int i=0;i

풀이 매개변수를 이용한 이분탐색 알고리즘 문제였다. 처음에 문제의 조건에서 B의 크기에 간과하여 시간이 꽤 소요되었는데, cost를 계산 후 매개변수의 차이의 합을 저장하던 중 자료형의 크기를 훨씬 넘어버리는 케이스를 생각하지 못하였다. overflow가 발생하면 더이상 차이의 합을 저장하지 않고 bool 타입 변수를 true로 조정 후 break문을 사용하여 넘어가는게 핵심이었던 문제이다. #include #include #include #include using namespace std; long long N,B,ans; vector vec; int main(int argc, char** argv) { cin>>N>>B; vector vec(N); for(int i=0;i>vec[i]; } sort(..