일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- silver
- BOJ
- parametric search
- 추천
- 영어
- 알고리즘
- 리뷰
- 영화
- array
- usaco
- 수능
- 넷플릭스
- Recursive
- Netflix
- health
- 코딩 테스트
- BFS
- kakao
- 2020
- Algorithm
- 완전탐색
- benefits
- 카카오
- Greedy
- 나는솔로
- Movie
- review
- coding
- 백준
- 해설
Archives
- Today
- Total
Young
BOJ - 삼삼한 수 (17252) 본문
728x90
반응형
https://www.acmicpc.net/problem/17252
이 문제는 풀 수 있는 방법이 크게 두 가지가 있습니다.
1. 수학적 풀이
2. 완전탐색
수학적 풀이는 다음에 소개하기로 하고, 이번에는 완전탐색으로 푸는 방법을 소개하겠습니다.
아무래도 코딩 테스트에서 완전탐색이 자주 나오기 때문이죠.
약 3^21 정도면 2,147,483,647 을 넘어서게 됩니다.
그러므로 3^0부터 3^21 까지 1번 또는 0번 사용해서 만들 수 있는가를 알아내기 위한 완전탐색을
수행하면 시간복잡도는 O(2^N) 으로 최대 2^21 = 약1000000 으로 시간안에 충분히 가능합니다.
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
31
32
33
34
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> v;
ll k;
void sol(ll total, int cur) {
if (total == 0) { // total 이 0에 도달하게 되면 그러한 조합을 찾았으므로 종료합니다.
cout << "YES";
exit(0);
}
if (cur == v.size() || total < 0) return; // cur 이 v의 끝에 도달하거나, total 값이 0 아래로 떨어지게 되면 더이상 희망이 없으므로 return 합니다.
// 각 스텝에서 취할수 있는 액션은 두 가지 입니다.
sol(total, cur + 1); // 현재 스텝에서의 값을 사용하지 않는다.
sol(total - v[cur], cur + 1); // 현재 스텝에서의 값을 한 번 사용한다.
}
int main() {
ll a = 2147483647;
ll b = 1;
while (a >= b) {
v.push_back(b);
b *= 3;
}
cin >> k;
if(k != 0) sol(k, 0); // 0인 경우는 제외시켜 줍니다.
cout << "NO";
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
728x90
반응형
'코딩 테스트 대비 추천 문제' 카테고리의 다른 글
BOJ - 로봇 청소기 (4991) (1) | 2019.12.12 |
---|---|
BOJ - 복면산?! (15811) (0) | 2019.12.11 |
BOJ - N으로 만들기 (17255) (0) | 2019.12.09 |
BOJ - 주사위 윷놀이 (17825) [2019 삼성 SW 기출] (0) | 2019.12.07 |
BOJ - 공주님을 구해라! (17836) (0) | 2019.12.03 |