×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,191,133명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

문제 출처 :


https://www.acmicpc.net/problem/1351



알고리즘 분석 :


문제 해결에 필요한 사항

1. Dynamic Programming

2. Map STL


Map을 이용한 DP를 구하는 문제이다.


처음에는 다음과 같이 제출하여 TLE를 받게 되었다.


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
35
36
37
38
39
40
#include <iostream>
#include <cstdio>
using namespace std;
 
int A[3];
 
long long int p, q;
long long int ans;
 
void dfs(long long int n)
{
    if (n / p > 1)
        dfs(n / p);
 
    else
        ans += A[n / p];
 
    if (n / q > 1)
        dfs(n / q);
 
    else
        ans += A[n / q];
 
}
int main()
{
    long long int n;
    scanf("%lld %lld %lld"&n, &p, &q);
    A[0= 1;
    A[1= 2;
 
    dfs(n);
 
    printf("%lld", ans);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


이렇게 한다면 값은 나오지만, 값이 커질수록 이미 알고있는 값을 활용하지 못하게 되어 TLE가 난다.


그리고 배열을 통해 DP를 하게 된다면 n, p, q의 범위가 long long형이기에 배열을 그만큼 늘릴 수가 없다.


따라서 map을 통해 배열의 공간 활용도를 높이고, map에 DP값을 쌓음으로써 해결한다.


소스 코드 : 

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
35
36
37
38
#include <cstdio>
#include <map>
 
using namespace std;
 
typedef long long int lli;
 
lli n, p, q;
 
map<lli, lli> DP;
 
lli getDP(lli x)
{
    if (x == 0)
        return 1;
 
    else if (x == 1)
        return 2;
 
    // 해당 DP값이 존재한다면, DP를 리턴
    if (DP[x])
        return DP[x];
 
    // dfs를 통해 리턴 받게 된 값은 DP[x]에 저장한다.
    return DP[x] = getDP(x / p) + getDP(x / q);
}
 
int main()
{
    scanf("%lld %lld %lld"&n, &p, &q);
 
    printf("%lld\n\n", getDP(n));
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus

반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[1258번] 행렬찾기  (0) 2019.07.30
[1264번] 이미지 유사도 검사  (2) 2019.07.17
[1351번] 무한 수열  (0) 2019.07.14
[1808번] 지희의 고장난 계산기  (0) 2019.07.06
[1266번] 소수 완제품 확률  (0) 2019.07.03
[1269번] 대칭 차집합  (0) 2019.07.02