'알고리즘' 카테고리의 다른 글
| [EASY] 백준 2167 2차원 배열의 합 (0) | 2018.04.02 |
|---|---|
| [DP] 백준 14916 거스름돈 (0) | 2018.04.02 |
| [DP] 백준 동전 2 2294 (0) | 2018.04.02 |
| [DP] 백준 2011 암호코드 (0) | 2018.01.02 |
| [그래프] 백준 1987 알파벳 (0) | 2017.12.14 |
전체 글
- [DP] 백준 9084 동전 2018.04.02
- [DP] 백준 동전 2 2294 2018.04.02
- [DP] 백준 2011 암호코드 2018.01.02
[DP] 백준 9084 동전
2018. 4. 2. 12:47
if (sum == 0) {
return 1;
}
if (sum < 0) {
return 0;
}
if (cache[sum][index] != -1) {
return cache[sum][index];
}
여기서 cache를 if 앞에 놔두면 런타임 에러가 났다.
이 코드가 왜 성공하는지 100% 는 이해 못했지만 계속 하다보면 될 것 같다. 한발짝 나간 것 같다.
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int n;
int money;
int arr[21];
int cnt;
int cache[10011][100];
int go(int sum,int index) {
if (sum == 0) {
return 1;
}
if (sum < 0) {
return 0;
}
if (cache[sum][index] != -1) {
return cache[sum][index];
}
cache[sum][index]++;
int& ret = cache[sum][index];
for (int i = index; i < n; ++i) {
ret += go(sum - arr[i],i);
}
return ret;
}
int main(void)
{
int t;
cin >> t;
while (t--) {
memset(arr, 0, sizeof(arr));
memset(cache, -1, sizeof(cache));
cnt = 0;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> arr[i];
}
cin >> money;
cout << go(money,0) << endl;
}
return 0;
}
[DP] 백준 동전 2 2294
2018. 4. 2. 12:45
최적화
안되는 경우는 money의 최댓값인 10000을 넘는 것을 리턴할 때 -1을 출력하도록 했다.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <limits.h>
using namespace std;
int table[10001];
int cache[10001];
bool visited[10001];
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };
int n;
int go(int money) {
//cout << money << endl;
if (money == 0) {
return cache[money];
}
if (money < 0) {
return 10001;
}
int& ret = cache[money];
if (ret != -1) {
return ret;
}
cache[money] = INT32_MAX;
for (int i = 0; i < n; ++i) {
ret = min(ret, 1 + go(money - table[i]));
}
return ret;
}
int main(void) {
memset(cache, -1, sizeof(cache));
int money;
cin >> n >> money;
for (int i = 0; i < n; ++i) {
cin >> table[i];
}
int ans = go(money);
cout << (ans>10000 ? -1 : ans+1) << endl;;
return 0;
}
'알고리즘' 카테고리의 다른 글
| [DP] 백준 14916 거스름돈 (0) | 2018.04.02 |
|---|---|
| [DP] 백준 9084 동전 (0) | 2018.04.02 |
| [DP] 백준 2011 암호코드 (0) | 2018.01.02 |
| [그래프] 백준 1987 알파벳 (0) | 2017.12.14 |
| [그래프] 백준 5567 결혼식 (0) | 2017.12.13 |
[DP] 백준 2011 암호코드
2018. 1. 2. 22:56
boj.kr/2011
수가 아무것도 없을 때는 그 자체도 한가지 경우라고 볼 수 있으므로
=> d[0] = 1;
수가 1개 있을 때의 경우의 수는 1가지
d[1] = 1;
수가 2개 있을 때의 경우의 수는
각자 하나씩의 알파벳을 나타내는 경우의 한가지와
만약 두 숫자를 합쳐서 나타낼 수 있는 26 이하의 숫자라면 한가지가 더 추가되어
한가지 또는 두가지가 된다.
#include <iostream>
#include <string>
#define mod 1000000
using namespace std;
long long d[5001];
int main() {
string s;
cin >> s;
int len = s.size();
s = " " + s;
d[0] = 1;
for (int i = 1; i <= len; ++i) {
int x = s[i] - '0';
if (1 <= x && x <= 9) {
d[i] = (d[i] + d[i - 1]) % mod;
}
if (i == 1) continue;
if (s[i - 1] == '0') continue;
x = (s[i - 1] - '0') * 10 + (s[i] - '0');
if (10 <= x && x <= 26) {
d[i] = (d[i] + d[i - 2]) % mod;
}
}
cout << d[len];
return 0;
}
'알고리즘' 카테고리의 다른 글
| [DP] 백준 9084 동전 (0) | 2018.04.02 |
|---|---|
| [DP] 백준 동전 2 2294 (0) | 2018.04.02 |
| [그래프] 백준 1987 알파벳 (0) | 2017.12.14 |
| [그래프] 백준 5567 결혼식 (0) | 2017.12.13 |
| [EAZY] 백준 1065번 한수 (0) | 2017.08.17 |