2853 배

2853 배 https://www.acmicpc.net/problem/2853

1일날에 모든 배가 들어온다.
그 후 한척이라도 배가 들어오면 이 날을 기록하였다.
배가 주기적으로 온다고 했을 때 방문한 배의 최소 개수를 구하는 문제이다.

수열에서 등차수열을 만족하는 최소 개수를 구하는 문제와 동치가 된다.
greedy하게 해결하였다.
index를 1부터 시작시킬 때 만약 해당 수열을 이미 방문했다면 건너 뛰고 아니라면
그에 해당하는 등차수열들을 방문한다.

#include <cstdio> #include <algorithm> #include <unordered_map> using namespace std; int N; int arr[5001]; bool chk[5001]; unordered_map<int,int> save; int ans, cnt; int main() {     scanf("%d", &N);     for (int n = 0;n < N;n++) scanf("%d", &arr[n]), save[arr[n]] = n;     chk[0] = true;     for (int n = 1;n < N;n++) {         if (chk[n]) continue;         int diff = arr[n] - 1;         ans++;         for (int m = arr[n];m <= arr[N - 1];m += diff) {             int idx = save[m];             if (!chk[idx]) {                 chk[idx] = true;                 cnt++;             }         }         if (cnt == N - 1) break;     }     printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs