반응형 컴퓨터 사이언스65 [c++] 백준 #3163 떨어지는 개미 (190915) 약간의 관찰이 필요한 문제이다. 개미가 서로 부딫히면 방향을 바꾼다고 해서 겁먹고 시뮬레이션처럼 구하면 시간초과이다. (물론 난 그러지 않았다.) 개미가 서로 부딫히면 방향을 바꾼다는 의미는 부딫힌 개미와 떨어지는 데 걸리는 시간이 swap된다는 것이다. 그래서 이렇게 swap이 반복되고 나면(약간의 손계산으로 직접 해보면 알 수 있다) 최종적으로, 각 개미의 방향은 ← ← ← ← → → → 이런식으로 되서 다리 밖으로 떨어질 것이다. swap되는 시간도 고려해보면 최종적으로 각 개미가 떨어지는 데 걸리는 시간은 정렬된 배열의 무언가와 닮아 있는데, -2 -3 -4 -5 7 3 2 1 이런 식으로 음수의 거리 값은 오름차순, 양수의 거리 값은 내림차순으로 정렬한 꼴로 정렬이 된다. 이제 각 .. 2019. 10. 8. [c++] 백준 #11568 민균이의 계략 (190915) 딱 봤을 때 DP문제 같았다. 가장 긴 증가하는 부분 수열 구하기 문제이다. 1) O(N^2) 풀이 (N #include using namespace std; #define INF 987654321 typedef long long ll; typedef pair ii; typedef tuple iii; #define pb push_back int main(){ ios::sync_with_stdio(false); cin.tie(0); int N; cin >> N; vector A(N, 0); vector DP(N, 1); // DP[i] = A[i]를 포함한 부분 수열 중 가장 긴 것의 길이 // 자기 자신만 포함하는 경우를 대비하여 1로 초기화 for(int i=0; i> A[i]; } int.. 2019. 10. 8. [c++] 백준 #2613 숫자구슬 (190903) 최댓값이 N이하가 되도록 구슬을 나눌 수 있을까? 라는 질문으로 바꾸고 Binary search를 이용하면 된다. 이는 맨 앞에서부터 구슬을 하나씩 꽉꽉 채운다고 하면 한 번 search할 때마다 O(n)에 해결 가능하다. 최댓값을 기준으로 그룹을 나누면 m > M; for(int i=0; i> ball[i]; } int low = 0; int high = (N / M) * 100; //max value int mid; int ans = INF; while(low 2019. 10. 8. [c++] 백준 #1162 도로포장 (190903) 다익스트라 알고리즘에 DP를 곁들인듯한 그런 문제이다. 무시 가능한 남은 도로의 개수를 dp로 계산해줘야 한다. dp[a][k]는 a까지 가는데 무시 가능한 도로의 남은 개수가 k개 있을 때를 의미하는데, 다익스트라에서 현재 edge를 무시한 cost를 dp[a][k-1]에, 합한 cost를 dp[a][k]에 넣어주면 된다. 그 이후 dp[N][0]~dp[N][K]까지 min값을 취하면 된다. 이 때 cost 값이 int형을 넘어갈 수 있으니 long long의 max값인 9223372036854775807 ? 이라는 값으로 INF를 바꿔주어야 한다. 직접 생각한 풀이는 아닌데 해보니까 생각보다 어렵지는 않았던 문제이다. #include using namespace std; .. 2019. 10. 8. 이전 1 ··· 5 6 7 8 9 10 11 ··· 17 다음 반응형