[Algorithm]Boj 2422 cpp
-
2422
-
아이스크림 종류 N, 피해야 할 조합 수 M개가 주어진다.
-
그 다음 M 줄로 피해야할 두 아이스크림의 조합이 주어진다.
풀이
-
가능한 모든 아이스크림의 조합을 모두 돌리면서 (완전탐색)
-
피해야 할 조합을 모두 돌려보면서, 돌리고 있는 아이스크림의 조합이 피해야할 조합을 가지고있다면 그냥 끝낸다.
-
만약 피해야 할 조합을 모두 통과했다면 count를 증가시켜준다.
-
위 방법대로 하면 시간초과가 뜬다.
-
200 199 198 * 10000 = 788억이기 때문..
-
그럼 줄일 수 있는게 어떤게 있을까?
-
아이스크림은 모두 확인을 해봐야 하긴 한다. 왜냐면 가능한 가짓수를 세야하니까..
-
그러면 check하는 저 연산을 줄여야 하는데, 어떻게 하면 두 조합을 묶어서 의미있게 저장할 수 있으며 동시에 신속하게 할 수 있을까?
-
나 같은 경우 처음엔 pair를 사용해서 구현하였다.
-
배열을 생각하지 않았던게, 1차원 배열에 구현한다면 피하지 않아도 될 조합도 check에서 통과되지 않을 수 있기 때문이다.
-
하지만 2차원배열을 생각을 못했다.. 2차원 배열을 이용한다면 속도가 빠르게 구현이 가능하다.
-
주의해야 할 점은, 피해야 할 조합은 오름차순으로 들어오지 않을 수 있다.
-
따라서 2차원 배열의 행(왼쪽거) 보다 열(오른쪽거) 이 더 크도록 넣어주면 오름차순으로 넣어줄 수 있고, 가능한 아이스크림의 조합을 돌릴때 오름차순으로 넣어주면 정확하게 비교할 수 있다.
코드
#include <iostream> #include <vector> using namespace std; int check_list[200][200]; int check(int i, int j, int k) { if (check_list[i][j] != 1 && check_list[j][k] != 1 && check_list[i][k] != 1) return (1); return (0); } int run(int N) { int count = 0; for (int i = 0; i < N - 2; i++) for (int j = i + 1; j < N - 1; j++) for (int k = j + 1; k < N; k++) if (check(i, j, k)) count++; return (count); } int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); int N, M; vector<pair<int, int> > sep; cin >> N >> M; for (int i = 0; i < M; i++) { int a, b; cin >> a >> b; a--; b--; if (a < b) check_list[a][b] = 1; else check_list[b][a] = 1; } cout << run(N) << endl; }
-
Author And Source
이 문제에 관하여([Algorithm]Boj 2422 cpp), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@modyhoon/AlgorithmBoj-2422-cpp저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)