'알고리즘' 카테고리의 다른 글
| [DP] 백준 9251 LCS (0) | 2018.04.29 |
|---|---|
| [DP] 백준 10942 팰린드롬? (0) | 2018.04.29 |
| [DP] 백준 2096 내려가기 (0) | 2018.04.29 |
| [DP] 백준 9507 Generations of Tribbles (0) | 2018.04.29 |
| [DP] 백준 1309 동물원 (0) | 2018.04.29 |
[DP] 백준 1890 점프, 3372 보드 점프 다시풀만한 것
2018. 4. 29. 00:32
마지막까지 간 횟수를 세면 된다고 생각해서 전역변수 cnt 를 기저사례안에서 ++시키면 구할 수 있을 것이라고 생각했다.
하지만 실제로 저 기저사례를 방문하는 횟수가 가능한 개수가 아니라 그 기저사례를 방문하기 전에 cache에 저장된 값이 기저사례에 방문하기 이전에 방문한 값을 저장하고 있다면
실제로 기저사례는 방문하지 않으면서 cache는 그 경우를 처리한다.
참조적 투명 함수에 대해 생각하고 전역변수는 최대한 안 쓰고 해결할 수 있게 해봐야 겠다.
아래 보드 점프 문제는 똑같은데 제한이 2^63-1 보다 큰 것도 온다. BigInt 라이브러리를 가지고 와서 사용했다.
//1890 점프
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll tb[1001][1001]; // tb == table
ll cch[1001][1001]; // cch == cache
ll n, cnt = 0;
ll go(ll x, ll y) {
if (x == y && y == n - 1) {
return 1;
}
/*if (tb[x][y] == 0) {
cch[x][y] = -1;
}*/
ll& ret = cch[x][y];
if (ret != -1) {
return ret;
}
ret = 0;
ll next = tb[x][y];
if (next > 0) {
if (x + next < n) {
ret += go(x + next, y);
}
if (y + next < n) {
ret += go(x, y + next);
}
}
return ret;
}
void process() {
cin >> n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> tb[i][j];
cch[i][j] = -1; // cahce init
}
}
//cout << (cch[n-1][n-1]==1 ? "YES" : "NO") << endl;
cout << go(0, 0) << endl;
return;
}
int main(void)
{
process();
return 0;
}
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stdlib.h>
#include <string>
using namespace std;
// Big Int 구현 library
typedef int64_t ll;
//typedef long long int ll;
typedef pair<ll, ll> lll;
typedef pair<ll, int> lli;
typedef pair<int, int> ii;
#define EL printf("\n")
#define OK printf("OK")
#define pb push_back
#define mp make_pair
#define ep emplace_back
#define X first
#define Y second
#define fillchar(a,x) memset(a, x, sizeof(a))
#define FOR(i,l,r) for (int i=l;i<=r;i++)
#define FORD(i,r,l) for (int i=r;i>=l;i--)
const int base = 1e9;
typedef vector<int> BigInt;
void Set(BigInt &a) {
while (a.size() > 1 && a.back() == 0) a.pop_back();
}
void Print(BigInt a) {
Set(a);
printf("%d", (a.size() == 0) ? 0 : a.back());
FORD(i, a.size() - 2, 0) printf("%09d", a[i]); EL;
}
BigInt Integer(string s) {
BigInt ans;
if (s[0] == '-') return ans;
if (s.size() == 0) { ans.pb(0); return ans; }
while (s.size() % 9 != 0) s = '0' + s;
for (int i = 0; i<s.size(); i += 9) {
int v = 0;
for (int j = i; j<i + 9; j++) v = v * 10 + (s[j] - '0');
ans.insert(ans.begin(), v);
}
Set(ans);
return ans;
}
BigInt Integer(char c[]) {
string s = "";
FOR(i, 0, strlen(c) - 1) s = s + c[i];
return Integer(s);
}
BigInt Integer(ll x) {
string s = "";
while (x > 0) s = char(x % 10 + '0') + s, x /= 10;
return Integer(s);
}
BigInt Integer(int x) {
return Integer((ll)x);
}
void operator >> (istream &in, BigInt &a) {
string s;
getline(cin, s);
a = Integer(s);
}
void operator << (ostream &out, BigInt a) {
Print(a);
}
bool operator < (BigInt a, BigInt b) {
Set(a);
Set(b);
if (a.size() != b.size()) return (a.size() < b.size());
FORD(i, a.size() - 1, 0)
if (a[i] != b[i]) return (a[i] < b[i]);
return false;
}
bool operator > (BigInt a, BigInt b) {
return (b < a);
}
bool operator == (BigInt a, BigInt b) {
return (!(a < b) && !(b < a));
}
bool operator <= (BigInt a, BigInt b) {
return (a < b || a == b);
}
bool operator >= (BigInt a, BigInt b) {
return (b < a || b == a);
}
bool operator < (BigInt a, int b) {
return (a < Integer(b));
}
bool operator > (BigInt a, int b) {
return (a > Integer(b));
}
bool operator == (BigInt a, int b) {
return (a == Integer(b));
}
bool operator >= (BigInt a, int b) {
return (a >= Integer(b));
}
bool operator <= (BigInt a, int b) {
return (a <= Integer(b));
}
BigInt max(BigInt a, BigInt b) {
if (a > b) return a;
return b;
}
BigInt min(BigInt a, BigInt b) {
if (a < b) return a;
return b;
}
BigInt operator + (BigInt a, BigInt b) {
Set(a);
Set(b);
BigInt ans;
int carry = 0;
FOR(i, 0, max(a.size(), b.size()) - 1) {
if (i < a.size()) carry += a[i];
if (i < b.size()) carry += b[i];
ans.pb(carry%base);
carry /= base;
}
if (carry) ans.pb(carry);
Set(ans);
return ans;
}
BigInt operator + (BigInt a, int b) {
return a + Integer(b);
}
BigInt operator ++ (BigInt &a) { // ++a
a = a + 1;
return a;
}
void operator += (BigInt &a, BigInt b) {
a = a + b;
}
void operator += (BigInt &a, int b) {
a = a + b;
}
BigInt operator - (BigInt a, BigInt b) {
Set(a);
Set(b);
BigInt ans;
int carry = 0;
FOR(i, 0, a.size() - 1) {
carry += a[i] - (i < b.size() ? b[i] : 0);
if (carry < 0) ans.pb(carry + base), carry = -1;
else ans.pb(carry), carry = 0;
}
Set(ans);
return ans;
}
BigInt operator - (BigInt a, int b) {
return a - Integer(b);
}
void operator -- (BigInt &a) { // --a
a = a - 1;
}
void operator -= (BigInt &a, BigInt b) {
a = a + b;
}
void operator -= (BigInt &a, int b) {
a = a - b;
}
BigInt operator * (BigInt a, BigInt b) {
Set(a);
Set(b);
BigInt ans;
ans.assign(a.size() + b.size(), 0);
FOR(i, 0, a.size() - 1) {
ll carry = 0ll;
for (int j = 0; j<b.size() || carry > 0; j++) {
ll s = ans[i + j] + carry + (ll)a[i] * (j<b.size() ? (ll)b[j] : 0ll);
ans[i + j] = s % base;
carry = s / base;
}
}
Set(ans);
return ans;
}
BigInt operator * (BigInt a, int b) {
return a * Integer(b);
}
void operator *= (BigInt &a, BigInt b) {
a = a * b;
}
void operator *= (BigInt &a, int b) {
a = a * b;
}
BigInt operator / (BigInt a, BigInt b) {
Set(a);
Set(b);
if (b == Integer(0)) return Integer("-1");
BigInt ans, cur;
FORD(i, a.size() - 1, 0) {
cur.insert(cur.begin(), a[i]);
int x = 0, L = 0, R = base;
while (L <= R) {
int mid = (L + R) >> 1;
if (b*Integer(mid) > cur) {
x = mid;
R = mid - 1;
}
else
L = mid + 1;
}
cur = cur - Integer(x - 1)*b;
ans.insert(ans.begin(), x - 1);
}
Set(ans);
return ans;
}
BigInt operator / (BigInt a, int b) {
Set(a);
BigInt ans;
ll cur = 0ll;
FORD(i, a.size() - 1, 0) {
cur = (cur*(ll)base + (ll)a[i]);
ans.insert(ans.begin(), cur / b);
cur %= b;
}
Set(ans);
return ans;
}
void operator /= (BigInt &a, BigInt b) {
a = a / b;
}
void operator /= (BigInt &a, int b) {
a = a / b;
}
BigInt operator % (BigInt a, BigInt b) {
Set(a);
Set(b);
if (b == Integer(0)) return Integer("-1");
BigInt ans;
FORD(i, a.size() - 1, 0) {
ans.insert(ans.begin(), a[i]);
int x = 0, L = 0, R = base;
while (L <= R) {
int mid = (L + R) >> 1;
if (b*Integer(mid) > ans) {
x = mid;
R = mid - 1;
}
else
L = mid + 1;
}
ans = ans - Integer(x - 1)*b;
}
Set(ans);
return ans;
}
int operator % (BigInt a, int b) {
Set(a);
if (b == 0) return -1;
int ans = 0;
FORD(i, a.size() - 1, 0)
ans = (ans*(base%b) + a[i] % b) % b;
return ans;
}
void operator %= (BigInt &a, BigInt b) {
a = a % b;
}
void operator %= (BigInt &a, int b) {
a = a % Integer(b);
}
BigInt gcd(BigInt a, BigInt b) {
Set(a);
Set(b);
while (b > Integer(0)) {
BigInt r = a % b;
a = b;
b = r;
}
Set(a);
return a;
}
BigInt lcm(BigInt a, BigInt b) {
return (a*b / gcd(a, b));
}
BigInt sqrt(BigInt a) {
BigInt x0 = a, x1 = (a + 1) / 2;
while (x1 < x0) {
x0 = x1;
x1 = (x1 + a / x1) / 2;
}
return x0;
}
BigInt pow(BigInt a, BigInt b) {
if (b == Integer(0)) return Integer(1);
BigInt tmp = pow(a, b / 2);
if (b % 2 == 0) return tmp * tmp;
return tmp * tmp * a;
}
BigInt pow(BigInt a, int b) {
return pow(a, (Integer(b)));
}
int log(int n, BigInt a) { // log_n(a)
Set(a);
int ans = 0;
while (a > Integer(1)) {
ans++;
a /= n;
}
return ans;
}
// Big Int 구현 library 끝
int tb[1001][1001]; // tb == table
BigInt cch[1001][1001]; // cch == cache
int n, cnt = 0;
BigInt go(int x, int y) {
if (x == y && y == n - 1) {
return Integer(1);
}
/*if (tb[x][y] == 0) {
cch[x][y] = -1;
}*/
BigInt& ret = cch[x][y];
if (ret != Integer(-1)) {
return ret;
}
ret = Integer(0);
int next = tb[x][y];
if (next > 0) {
if (x + next < n) {
ret += go(x + next, y);
}
if (y + next < n) {
ret += go(x, y + next);
}
}
return ret;
}
void process() {
cin >> n;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> tb[i][j];
cch[i][j] = Integer(-1); // cahce init
}
}
//cout << (cch[n-1][n-1]==1 ? "YES" : "NO") << endl;
Print(go(0, 0));
return;
}
int main(void)
{
process();
return 0;
}