#문제

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

 

4781번: 사탕 가게

문제 상근이는 선영이와 걸어가다가 사탕 가게를 지나가게 되었다. 갑자기 상근이는 선영이에게 사탕이 얼마나 건강에 안 좋은지 설명하기 시작했다. 선영이는 매우 짜증이 났고, 상근이에게 누가 더 건강이 안 좋아질 수 있는지 내기를 하자고 했다. 상근이는 내기를 그 즉시 받아들였다. 두 사람은 같은 돈을 가지고 가게에 들어가서 사탕을 산다. 이때, 구매한 사탕의 칼로리가 더 큰 사람이 내기에서 이기게 된다. 상근이는 잠시 화장실에 갔다온다고 핑계를 댄 뒤에,

www.acmicpc.net

 

#작성 코드

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
41
42
43
44
45
#include <iostream>
using namespace std;
 
int n, M;
    // M : m*100    (dp 배열의 인덱스로 가격을 사용하기 위해.) 
int candy[5000][2];
            // [0] : 칼로리
            // [1] : 가격*100 
int dp[10001];
            // 0 ~ 10000을 사용한다. 
 
int main(){
    while(true){ 
        double m;
        cin>>n>>m;
        if( n==0 ) break;        // 0 0.00을 입력받으면 테스트케이스 입력을 끝마친다. 
        M = (int)(m*100+0.5);
        
        // n개의 사탕 정보 저장
        for(int i=0; i<n; i++){
            int c, P; double p;
            cin>>c>>p;
            P = (int)(p*100+0.5);
            candy[i][0] = c;
            candy[i][1] = P;
        }
        fill_n(dp, 10001, 0);
        
        // 돈 m을 가지고 구매할 수 있는 최대 칼로리를 구한다.
        for(int i=0; i<n; i++){
            int cal = candy[i][0];
            for(int ii= candy[i][1]; ii<=M; ii++){
                dp[ii] = max(dp[ii], dp[ii-candy[i][1]]+cal); 
            }
        }
        
        // 최대 칼로리를 찾아 출력한다.
        int result=0;
        for( int i=0; i<10001; i++ ){
            result = max(result, dp[i]);
        }
        cout<<result<<'\n';
    }
    return 0;
} 
 cs

##

7579번 문제와 유사하다는 글을 읽고 복습할 겸 풀어보았다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 10942번 :: 팰린드롬?  (0) 2020.01.28
BOJ 2261번 :: 가장 가까운 두 점  (0) 2020.01.27
BOJ 7579번 :: 앱  (0) 2020.01.23
BOJ 1520번 :: 내리막 길  (0) 2020.01.09
BOJ 12015번 :: 가장 긴 증가하는 부분 수열 2  (0) 2020.01.06

#문제

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

 

#작성 코드

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
41
42
43
44
#include <iostream>
#include <vector>
using namespace std;
 
int n, M;
vector<int> mem;
vector<int> cost;
int d[10001]; 
    // d[cost]에 cost를 만족하는 최대로 확보 가능한 메모리 크기를 저장한다. 
 
int main(){
    // 입 력 
    cin>>n>>M;
    for(int i=0; i<n; i++){
        int m;
        cin>>m;
        mem.push_back(m);
    }
    for(int i=0; i<n; i++){
        int c;
        cin>>c;
        cost.push_back(c);
    }
    // d배열 값을 모두 -1로 초기화
    fill_n(d, 10001, -1); 
    
    // 필요한 메모리 M바이트를 확보하기 위한 앱 비활성화의 최소비용 계산.
    for(int i=0; i<n; i++){
        int c = cost[i];
        for(int j=10000; j>=c; j--){
            if( d[j-c]==-1 ) continue;    // 계산된적있는 j-c에 대해서만 계산 
            d[j] = max(d[j], d[j-c]+mem[i]);
            // i번째 app을 포함하는 경우와 포함하지 않는 경우 중 확보 메모리가 더 큰 경우 저장. 
        }
        if( d[c]<mem[i] ) d[c] = mem[i];
    }
    for(int i=0; i<10001; i++){
        if( d[i] >= M ){
        // 작은 cost부터 탐색, 최초로 확보 메모리가 M 이상인 경우 cost 출력 
            cout<<i<<'\n';
            return 0;
        }
    }
}
 cs

##

메모리 확보를 위한 앱 비활성화는 1회만 가능하기 때문에(4781번 사탕가게 문제처럼 한 종류의 사탕을 여러번 사는 것이 불가능.)

for(int j=10000; j>=c; j--){} 와 같이 cost를 역순으로 줄여나가며 메모이제이션을 수행한다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 2261번 :: 가장 가까운 두 점  (0) 2020.01.27
BOJ 4781번 :: 사탕가게  (0) 2020.01.23
BOJ 1520번 :: 내리막 길  (0) 2020.01.09
BOJ 12015번 :: 가장 긴 증가하는 부분 수열 2  (0) 2020.01.06
BOJ 11055번 :: 가장 큰 증가 부분 수열  (0) 2020.01.06

#문제

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

 

1520번: 내리막 길

첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.

www.acmicpc.net

 

#작성 코드

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
41
42
43
44
#include <iostream>
using namespace std;
 
int m, n;
// map과 dp배열 (1,1) ~ (m,n) 사용 
int map[501][501];
int dp[501][501];
int d[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
 
bool isIn(int x, int y){
    return x>=1&&x<=m&&y>=1&&y<=n;
}
 
int downhill(int x, int y){
    if( dp[x][y]!=-1 ) return dp[x][y];    // 이미 계산한 적 있다면 그 값 리턴 
    if( !isIn(x, y)) return 0;            // 범위를 벗어났다면 그 곳까지 가는 경우의 수는 0이다 
    if( x==1 && y==1 ) return 1;        //(1,1)에서 출발해서 (1,1)에 도착하는 경우의 수 : 1 
    
    dp[x][y] = 0;        // dp를 새로 계산할 때는 0으로 초기화하고 더해야한다. 
     
    for(int di=0; di<4; di++){
        // (x,y)의 상하좌우 탐색 
        int nextX = x+d[di][0];
        int nextY = y+d[di][1];
        // (x,y)보다 (nextX,nextY)의 높이가 높다면
        // (x,y)까지 가는 경우의 수 += 각 (nextX,nextY)까지 가는 경우의 수 
        if( map[nextX][nextY] > map[x][y] ){
            dp[x][y] += downhill(nextX, nextY);
        }
    }
    // 계산된 (x,y)까지 가는 경우의 수를 리턴한다. 
    return dp[x][y];    
}
int main(){
    cin>>m>>n;
    for(int i=1; i<=m; i++){
        for(int j=1; j<=n; j++){
            cin>>map[i][j];
            dp[i][j]=-1;    // dp배열 -1로 초기화. 
        }
    }
    cout<<downhill(m,n)<<'\n';
    return 0;
}
 cs

##

bfs로 할 수 있을까? 하다가 dfs로 시도해보았다.

' (x,y)까지 가는 경우의 수 : (x,y)상하좌우 중에서 그보다 높이가 높은 곳까지 가는 경우의 수의 합 ' 이 부분이 가장 중요한 부분이다.

dp를 이용해서 한번 계산한 경우의 수에 대해서는 그 값을 그대로 불러와서 다시 계산하지 않도록 하였다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 4781번 :: 사탕가게  (0) 2020.01.23
BOJ 7579번 :: 앱  (0) 2020.01.23
BOJ 12015번 :: 가장 긴 증가하는 부분 수열 2  (0) 2020.01.06
BOJ 11055번 :: 가장 큰 증가 부분 수열  (0) 2020.01.06
BOJ 11049번 :: 행렬 곱셈 순서  (0) 2020.01.06

#문제

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

 

12015번: 가장 긴 증가하는 부분 수열 2

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

www.acmicpc.net

 

#작성 코드

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
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n;
int serial[1000001];
vector<int> asc;
 
int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>serial[i];
    }
    
    for(int i=1; i<=n; i++){
        if( asc.empty() ){
            asc.push_back(serial[i]);
            continue;
        }
        else{
            if( asc.back() < serial[i] ){
                asc.push_back(serial[i]);
                continue;
            }
            else{
                vector<int>::iterator iter = lower_bound(asc.begin(), asc.end(), serial[i]);
                *iter = serial[i];
                // asc에서 serial[i]보다 최초로 큰 원소를 찾고, serial[i]로 대체한다. 
                continue; 
            }
        }
    }
    cout<<asc.size()<<'\n';
    return 0;
}
cs

##

이분탐색으로 어떻게 푸는 것이 좋을지 전혀 떠오르지 않아서

https://ferrante.tistory.com/54, https://mygumi.tistory.com/303?category=677288 참고하여 이분탐색으로 푸는 방법을 공부했다.

 

lower_bound 함수와 upper_bound 함수는 <algorithm> 헤더파일에 포함되어 있는 함수.

https://okayoki2484.tistory.com/135

 

BOJ 10816번 :: 숫자 카드 2

#문제 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진..

okayoki2484.tistory.com

 

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 7579번 :: 앱  (0) 2020.01.23
BOJ 1520번 :: 내리막 길  (0) 2020.01.09
BOJ 11055번 :: 가장 큰 증가 부분 수열  (0) 2020.01.06
BOJ 11049번 :: 행렬 곱셈 순서  (0) 2020.01.06
BOJ 2193번 :: 이친수  (0) 2020.01.05

#문제

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

 

11055번: 가장 큰 증가 부분 수열

수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.

www.acmicpc.net

 

#작성 코드

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
#include <iostream>
using namespace std;
 
int n;
int serial[1001];
int partsum[1001];
// 인덱스 1~min(1000, n)까지 사용. 
 
int main(){
    // 입력 및 초기화 
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>serial[i];
        
    partsum[1] = serial[1];
    int partsumMax=partsum[1];
    
    // 가장 긴 증가하는 부분수열의 합 구하기 
    for(int i=2; i<=n; i++){
        partsum[i] = serial[i];        // 본인만 포함하는 가장 작은 케이스에서 시작. 
        for(int j=1; j<=i; j++){
            if( serial[i]>serial[j] && partsum[j]+serial[i] > partsum[i]){
                partsum[i] = partsum[j] + serial[i];
            }
        }
        partsumMax = max(partsumMax, partsum[i]); 
    }
    cout<<partsumMax<<'\n';
    return 0;
}
 cs

##

LIS를 복습하며 비슷한 문제를 풀어보았다.

 

나를 포함하는 증가수열 중에서 증가수열 원소의 합이 최대가 될 때를 partsum[]에 저장한다.

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 1520번 :: 내리막 길  (0) 2020.01.09
BOJ 12015번 :: 가장 긴 증가하는 부분 수열 2  (0) 2020.01.06
BOJ 11049번 :: 행렬 곱셈 순서  (0) 2020.01.06
BOJ 2193번 :: 이친수  (0) 2020.01.05
BOJ 11057번 :: 오르막 수  (0) 2020.01.05

#문제

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

 

11049번: 행렬 곱셈 순서

첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다.

www.acmicpc.net

 

#작성 코드

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
#include <iostream>
using namespace std;
 
int n;
int mat[501][2];
int INF = 987654321;
int dp[501][501];
 
int calMin(int s, int e){
    if( dp[s][e]!=INF )
        return dp[s][e];
    if( s==e )
        return dp[s][e]=0;
    if( s+1 == e )
        return dp[s][e] = mat[s][0]*mat[s][1]*mat[e][1];
    
    for(int mid=s; mid<e; mid++){
        int left = calMin(s, mid);
        int right = calMin(mid+1, e);
        dp[s][e] = min(dp[s][e], (left+right)+(mat[s][0]*mat[mid][1]*mat[e][1]));
    }
    return dp[s][e];
}
 
int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>mat[i][0]>>mat[i][1];
    }
    // dp배열 INF로 초기화 
    for(int i=0; i<501; i++){
        for(int j=0; j<501; j++){
            dp[i][j] = INF;
        }
    }
    
    cout<<calMin(1, n)<<'\n';
    return 0;
}
 cs

##

11066번 파일 합치기 문제와 비슷!

저작자표시 비영리

'BOJ' 카테고리의 다른 글

BOJ 12015번 :: 가장 긴 증가하는 부분 수열 2  (0) 2020.01.06
BOJ 11055번 :: 가장 큰 증가 부분 수열  (0) 2020.01.06
BOJ 2193번 :: 이친수  (0) 2020.01.05
BOJ 11057번 :: 오르막 수  (0) 2020.01.05
BOJ 9095번 :: 1, 2, 3 더하기  (0) 2020.01.05

+ Recent posts

티스토리툴바