티스토리 뷰
문제
17436번: 소수의 배수
첫째 줄에 N(1 ≤ N ≤ 10)과 M(1 ≤ M ≤ 1012)이 주어진다. 둘째 줄에는 N개의 소수가 주어진다. 입력으로 주어지는 소수는 100보다 작거나 같으며, 같은 소수가 두 번 이상 주어지지 않는다.
www.acmicpc.net
문제 풀이
m의 범위를 못보고 계속 int형으로 제출해 삽푼문제였다.
1. 우선 m에 대해 각각의 소수로 나눴을 때 나누어 떨어지는 개수를 모두 세어보면 m/p[0] , m/p[1] ...등이 있을 것이다.
2. 이 때 간단한 예시를 통해 생각해보면 중복으로 카운트되는 수들이 존재하는 걸 알 수 있다.
- m = 30, p[0]= 2 ,p[1] = 3 일 때, p[0]에선 2,4,6...30 p[1]에선 3,6,9...30 // 6의 배수가 중복으로 카운트
3. 백트래킹으로 가능한 소수의 조합을 모두 구한뒤, 포함배제원리를 사용해 개수를 관리해준다.
코드
#include <bits/stdc++.h>
using namespace std;
int n;
long long m, ans, gop;
vector<int> p, picked;
void go(int st, int topick) {
if (topick == 0) {
gop = 1;
for (int i : picked) gop *= p[i];
if (picked.size() % 2) ans += m / gop;
else ans -= m / gop;
return;
}
for (int i = st + 1; i < n; i++) {
picked.push_back(i);
go(i, topick - 1);
picked.pop_back();
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> n >> m;
p.resize(n);
for (int i = 0; i < n; i++)
cin >> p[i];
for (int i = 1; i <= n; i++)
go(-1, i);
cout << ans;
}
'Algorithm > BOJ' 카테고리의 다른 글
[백준 3673] 나눌 수 있는 부분 수열 (0) | 2020.09.08 |
---|---|
[백준 1655] 가운데를 말해요 (0) | 2020.09.06 |
[백준 16402] 제국 (0) | 2020.09.05 |
[백준 19576] 약수 (0) | 2020.08.31 |
[백준 19588] 상품권 준비 (0) | 2020.08.31 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 2021 KAKAO BLIND
- 유니온파인드
- BFS
- 투포인터
- 표 편집
- DP
- 프로그래머스 위클리 9주차
- 프로그래머스 월간코드챌린지
- 누적합
- 이분탐색
- Kakaoblind
- 게임이론
- 카카오 2020 인턴십
- 트리
- 동적계획법
- 프로그래머스
- 백준
- 2022 KAKAO BLIND RECRUITMENT
- 카카오 인턴십
- 위클리 챌린지
- 카카오 2021
- 2022 카카오 블라인드 코딩테스트
- 카카오 표 편집
- 2022 카카오블라인드
- 시뮬레이션
- 2020 KAKAO BLIND RECRUITMENT
- 구현
- 2021 카카오 블라인드
- 카카오 2차코딩테스트
- 파싱
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
글 보관함