[문제 링크]



문제 의도는 스택으로 푸는 문제이지만, 굳이 스택으로 풀지 않아도 되는 문제이다.


그냥 레이저를 만났을 때, 여는 괄호의 갯수 만큼 더해줘도 되지만, 여기서는 스택을 이용해서 풀어보겠다.





이 문제를 풀기 위해선, 닫는 괄호가 나타났을 때, 이 것이 레이저인지, 아니면 파이프의 끝을 나타내는 것인지 구별해야 된다.

구별하는 방법은 정말 쉽다, 닫는 괄호가 나타났을 때, 바로 전 문자를 체크해서 이게 여는 괄호인지 아닌지만 확인하면 된다.

즉 여는 괄호를 만나면 전부 스택에 push하다가, 닫는 괄호를 만나면 스택에서 pop하고 괄호가 레이저면 스택 사이즈만큼 더해주거나, 파이프 끝이면 1만 더해주면 된다.


위 사진으로 예를 들어보자. 

처음에 '('를 만나서 스택에 push한다, 그리고 두번째에 ')'를 만난다. 스택에서 '('를 pop한다. 이전 문자는 '('이므로 레이저이다. 결과값에 스택 사이즈(0)만큼 더해준다.

result += 0


그다음 '('를 4개 만난다. 스택에 '('가 4개 들어가고 스택 사이즈는 4이다. ')'를 만나서 스택을 pop한다. 바로 전이 '('이므로 이는 레이저이다. 결과값에 스택 사이즈(3)만큼 더해준다.

result += 3


바로 다음에 괄호를 다시 여닫고 스택을 그에따라 push,pop해준다. 레이저이므로 스택 사이즈(3)을 다시 더해준다.

result += 3


닫는 괄호를 만난다. 바로 전 문자는 ')'이므로 레이저가 아닌 파이프의 끝이다. 파이프 꼭다리가 남으므로 1을 더해준다.


result +=1


위의 방법을 계속 반복하면 된다. 나머지는 직접 해보자.



이를 구현한 코드는 다음과 같다.


#include <iostream>
#include <string>
#include <stack>
using namespace std;
string str;
int pipe(const string& str){
    stack<char> st;
    int result=0;
    for(int i =0; i<str.length();i++){
        //여는 괄호면 스택에 넣는다. 
        if(str[i]=='(') st.push(str[i]);
        //닫는 괄호면 이 괄호가 레이저인지, 파이프 끝인지 알아본다.
        else{
            st.pop();
            //레이저면 
            if(str[i-1]=='(') 
                result += st.size(); //잘린 갯수 추가. 
            //파이프의 끝이면 
            else result++; //닫혀서 잘려진 갯수 추가. 
        }
    }
    return result;
}
int main(){ 
    cin >> str;
    cout<<pipe(str);
}


스택을 사용하지 않는 방법은 그냥 여는 괄호나 닫는 괄호를 만날 때, 갯수만 체크해주면 된다. 위에서 스택 사이즈를 체크한 것 대신에 갯수만 따로 저장하는 것이라고 보면 된다.


'Algorithm > Problems' 카테고리의 다른 글

백준 - 1725, 6549 히스토그램 / 알고스팟 - FENCE  (0) 2016.03.28
백준 - 2493 탑  (1) 2016.03.28
백준 - 1520 내리막 길  (0) 2016.03.15
백준 - 9465 스티커  (0) 2016.03.15
백준 - 1654 랜선자르기  (0) 2016.03.15


[문제 링크]


DP문제이다. 경로 모든 경로의 수를 구하는 미로 찾기와 같은 문제랑 다를게 없는데, 거기서 내리막으로만 갈 수 있다는 조건만 주면 되는 문제이다.

맵의 끝에 도달하면 1을 반환하고, 아닐 경우 0을 반환하여 경로의 갯수를 구한다.

밑은 이를 구현한 코드이다.


#include <cstdio>
#include <cstring>
int m,n,arr[501][501];
int relPos[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
int cache[501][501]; 
int dp(int y,int x){
    //기저사례 : 끝에 도달했으면 탈출 
    if(y==m && x==n) return 1;  
    int& ret = cache[y][x];
    if(ret!=-1) return ret;
    ret = 0;
    for(int c = 0; c<4; c++){
        int px = x + relPos[c][0];
        int py = y + relPos[c][1];
        //맵을 안넘어서고 내리막이면 
        if(px <=n && py<=m && px>=1 && py>=1&&arr[py][px] < arr[y][x])
            ret +=dp(py,px);
    }
    return ret;
} 
int main(){
    memset(cache,-1,sizeof(cache));
    scanf("%d %d",&m,&n);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&arr[i][j]);
        }
    }
    printf("%d",dp(1,1));
} 


경로 문제를 자주 보다보니 경로 문제는 이제 다 비슷비슷하다는 생각이 든다.

'Algorithm > Problems' 카테고리의 다른 글

백준 - 2493 탑  (1) 2016.03.28
백준 - 10799 쇠막대기  (2) 2016.03.28
백준 - 9465 스티커  (0) 2016.03.15
백준 - 1654 랜선자르기  (0) 2016.03.15
백준 - 1912 연속합  (0) 2016.03.07


[문제 링크]




DP문제이다. 어려운 문제는 아니고, 다음으로 선택할 수 있는 경로의 경우만 알면 쉽게 풀리는 문제인 것 같다.

자신을 기준으로 상하좌우는 접근할 수 없기 때문에, 대각선에 위치한 스티커나, 대각선에서 오른쪽으로 한칸 옆에 있는 스티커를 다음 경로로 선택하면 된다.

이렇게 모든 점수들을 더한 값 중 최대값을 구하면 되었다.

밑은 이를 구현한 코드이다.



#include <cstdio> #include <cstring> #include <algorithm> int t,n,arr[2][100000],cache[2][100000]; int relPos[4][2] = {{1,1},{1,-1},{2,-1},{2,1}}; int dp(int y, int x){ //기저사례 : y 끝에 도달했을 때 if(x==n-1) return arr[y][x]; int& ret = cache[y][x]; if(ret!=-1) return ret; ret = 0; for(int i=0;i<4;i++){ int px = x + relPos[i][0]; int py = y + relPos[i][1]; //스티커 범위를 초과하지 않으면 if(px<n&&px>=0&&py<2&&py>=0){ //최대값 구하기, 기존 ret와, 이 값+ 현재 좌표값 ret = std::max(ret,dp(py,px)+arr[y][x]); } } return ret; } int main(){ scanf("%d",&t); while(t--){ memset(cache,-1,sizeof(cache)); scanf("%d",&n); for(int y=0;y<2;y++){ for(int x=0;x<n;x++){ scanf("%d",&arr[y][x]); } } //(0,0)으로 시작할 때랑, (1,0)으로 시작할때 중 최댓값을 구하여 출력한다. printf("%d\n",std::max(dp(0,0),dp(1,0))); } }


'Algorithm > Problems' 카테고리의 다른 글

백준 - 10799 쇠막대기  (2) 2016.03.28
백준 - 1520 내리막 길  (0) 2016.03.15
백준 - 1654 랜선자르기  (0) 2016.03.15
백준 - 1912 연속합  (0) 2016.03.07
백준 - 2294 동전 2  (0) 2016.03.07




이전에 풀었던 문제인데, 재채점으로 인해 틀렸다하여 다시 풀었던 문제이다.(자료형만 바꿔주니 다시 맞게 나왔다.)

이분법으로 푸는 문제인데 이분 탐색에서 upper bound 방식으로 풀어야 한다.

왜냐하면 필요한 랜선의 길이인 N을 만드는 경우는 엄청 다양하기 때문이다. 그 다양한 길이 중 가장 긴 랜선의 길이를 찾아야한다.


밑은 이 문제의 코드이다.



#include <cstdio>
#include <algorithm>
long long k,n,l[10010], mi=0,m; 
long long bs(long long s, long long e) {
    //이분 탐색을 시작한다.
    while (s<=e) {
        m = (s + e) / 2;
        long long v = 0;
        // 각 종류의 랜선들을 현재의 길로 나눠 갯수를 구한다. 
        for (int i = 0; i < k; i++)
            v += l[i] / m;
            
        //갯수가 '같거나' 크면 m의 값을 1 증가시켜주고 이분탐색을 진행한다. 
        if (v >= n) s = m + 1;
        else if (v < n) e = m - 1;
    }
    return e;   
}
int main() {
    scanf("%lld %lld", &k, &n);
    for (int i = 0; i<k; i++) {
        scanf("%lld", &l[i]);
        mi = std::max(mi, l[i]);
    }
    printf("%lld",(n==1)?mi:bs(1, mi));
}

'Algorithm > Problems' 카테고리의 다른 글

백준 - 1520 내리막 길  (0) 2016.03.15
백준 - 9465 스티커  (0) 2016.03.15
백준 - 1912 연속합  (0) 2016.03.07
백준 - 2294 동전 2  (0) 2016.03.07
백준 - 2293 동전 1  (1) 2016.03.07


[문제 링크]


최대 연속합을 구하는 문제이다. 숫자 배열과, 최대 연속합을 저장하는 배열이 따로 더 필요하다.


구하고자 하는 숫자 배열의 가장 끝부터 차례로 내려가며, 최대연속합을 찾고자하는 배열값과, 바로 뒤 배열을 기점으로 하는 최대 연속합과의 합을 비교하여 그 최대값이 최대 연속 합이다.


밑은 예제를 돌렸을 경우의 CACHE 배열의 값이다. 맨 마지막의 CACHE값은 자기 뒤의 값이 없으므로 -1이 된다. 그 다음부터 재귀를 탈출해나가며 최대연속합을 구해나간다.


 ARR

 10

 -4

 3

 1

 5

 6

 -35

 12

 21

 -1

 CACHE

 21

 11

 15

 12

 11

 6

 -2

 33

 21

 -1


예를 들면 ARR이 21인 값은, 자신의 값 21과, 바로 뒤를 기점으로하는 최대 연속합과의 합인 21-1=20을 비교해서 큰 값이 그 위치를 기점으로하는 최대 연속합이다.

21인 경우에는 12와, 12+21=33 을 비교해서 큰 값이 그 위치를 기점으로하는 최대 연속합이다. 


즉 이 문제의 점화식은 다음과 같다.


DP(i) = MAX(arr[i], arr[i] + DP(i+1))



위 로직에 전체의 최대연속합을 저장하는 변수를 따로 만들어 답을 구하였다. 밑은 이를 구현한 코드이다.


#include <cstdio> #include <algorithm> int n,arr[100001],cache[100001]; int dp(int num){ //기저 사례 : 마지막에 도달했을 때, 마지막 값을 시작으로 하는 최대 연속합은 자기 자신이므로. if(num==n){ cache[n] = arr[n]; return arr[n]; } int& ret = cache[num]; //뒤의 값을 기준으로 하는 최대 연속값을 구하는 재귀 실행. int mx = dp(num+1); //점화식 : 자기 자신과, 바로 뒤의 값을 시작으로하는 최대 연속합과의 합중 최대값을 구한다. ret = std::max(arr[num],arr[num]+cache[num+1]); //지금까지 구한 연속합중 최대값을 구한다. mx = std::max(mx,ret); return mx; } int main(){ //초기화 scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&arr[i]); //구한 최대 연속합중 최대값을 찾는다. printf("%d",dp(1)); }


막상 풀고 보니 재귀로 푸는 것 보다 반복문이 훨씬 깔끔하게 나올 것 같았다. 밑은 재귀를 쓰지 않고 for문으로만 구한 코드이다.


#include <cstdio>
#include <algorithm>
int n,arr[100001],cache[100001];
int dp(){
    //가장 마지막 값은 그 자체가 최대연속합이므로 배열값을 넣어준다. 
    cache[n] = arr[n]; 
    int mx = arr[n];
    for(int i = n-1;i>0;i--){
        //점화식 : 자기 자신과, 바로 뒤의 값을 시작으로하는  최대 연속값과의 합중 최대값을 구한다.
        cache[i] = std::max(arr[i],arr[i]+cache[i+1]);
        //지금까지 구한 연속합중 최대값을 구한다.
        mx = std::max(mx,cache[i]);
    } 
    return mx;
}
int main(){
    //초기화 
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
    //구한 최대 연속합중 최대값을 찾는다. 
    printf("%d",dp());
}


'Algorithm > Problems' 카테고리의 다른 글

백준 - 9465 스티커  (0) 2016.03.15
백준 - 1654 랜선자르기  (0) 2016.03.15
백준 - 2294 동전 2  (0) 2016.03.07
백준 - 2293 동전 1  (1) 2016.03.07
백준 - 1697 숨바꼭질  (1) 2016.02.28


[문제 링크]


동전1에서 이어지는 문제다. 동전1은 경우의 갯수를 구하는 것이라면, 동전2 문제는 해당 경우에 사용되는 동전의 갯수를 구하는 것이다.


예를 들어 4원까지 동전 1,2만을 이용해서 갯수를 구하는 경우를 그려서 점화식을 구해보면



 

 1 동전 갯수

 2 동전 갯수

 DP(V)

 1일 때 DP(1)

 1 = DP(1-1)+1

 

 1

 2일 때 DP(2)

 2 = DP(2-1)+1

1 = DP(2-2)+1

 1

 3일 때 DP(3)

 3 = DP(3-1)+1

2 = DP(3-2)+1

 2

 4일 때 DP(4)

 4 = DP(4-1)+1

2 = DP(4-2)+1

 2


즉 DP(V) = min(DP(V), DV(V-COIN(i))+1) 의 점화식을 구할 수 있다.


다만 비교의 대상을 지정해야 하므로, 아무 값도 입력이 되어있지 않았을 때엔 최소 최적값 비교를 할 수 없기 때문에 DP(N) = DP(N- COIN(i)) + 1로 초기화 해주어야 한다.(초기화를 안해주면 DP(0)=0이므로 출력값은 0만 나온다..)


지금 동전 갯수를 구할 값이 초기화 된 값인지 아닌지, 이를 구하는데 필요한 이전 값이 초기화 되어있는지 조건을 걸어줘서 문제를 풀면 된다.


밑은 이를 구현한 코드이다.


#include <cstdio> #include <cstring> #include <algoritm> using namespace std; int n,coin[101],k,cache[10001]={0,}; int main(){ memset(cache,-1,sizeof(cache)); scanf("%d %d",&n,&k); for(int i=0;i<n;i++){ scanf("%d",&coin[i]); } cache[0] = 0; //각 동전별로 해당 값을 구하는데 드는 최소 횟수를 구한다. for(int i = 0; i<n; i++){ for(int j = 0; j<=k;j++){ if(j>=coin[i] && cache[j-coin[i]]!=-1){ //아무 값도 입력이 안됬을 경우엔 동전의 갯수를 초기화해준다. if(cache[j]==-1) cache[j] = cache[j-coin[i]]+1; //점화식, 값이 입력되어있으면 이전값과 비교해서 최소값을 넣어준다. else cache[j] = min(cache[j],cache[j-coin[i]]+1); } } } printf("%d",cache[k]); }


'Algorithm > Problems' 카테고리의 다른 글

백준 - 1654 랜선자르기  (0) 2016.03.15
백준 - 1912 연속합  (0) 2016.03.07
백준 - 2293 동전 1  (1) 2016.03.07
백준 - 1697 숨바꼭질  (1) 2016.02.28
백준 - 1005 ACM Craft  (0) 2016.02.27

[문제 링크]


DP문제이다. 정말 내 머리가 DP에서 틀에 박혔다는 생각이 든 문제였다. 원래는 DP[V] = DP[V] + DP[V-COIN[I]]와 같은 점화식으로 문제를 풀어나갔는데.


이 식의 문제점은 다른 순서지만, 같은 종류의 동전을 사용한 것도 모두 다른 값으로 취급해 카운트를 하는 것 같았다. 그래서 그냥 단순하게 위와 같은 방식으로 문제를 풀 경우 출력값이 엄청 크게 나왔다..


그래서 내가 원래 풀었던 것과 반복을 다른 방법으로 진행해야 하는데, 그것은 각 값 별로 방법의 수를 구하는 것이 아니라, 동전 별로 각 값에 대한 방법의 수를 구하는 것이다.



밑의 코드는 원래 방식대로, 값을 기준으로 재귀를 진행한 코드이다. 1,1,1,2와 2,1,1,1과 같은 같은 종류지만 다른 순서로 인것들도 모두 다른 경우로 취급해 엄청 큰 값이 나온다. 

각 동전의 경우에 따른 경우의 갯수를 cache의 2차원 배열로 추가하면 문제 해결이 가능하고, 실제로도 이렇게 답을 구했었지만 이 경우 문제의 메모리 제한 4mb를 초과해버린다.

#include <cstdio> #include <cstring> int n,coin[101],k,cache[10001]; //사용한 동전 갯수가 같으면 같은 경우이다. int dp(int value){ //기저사례 num == k일때 if(value==0) return 1; //기저사례 2, n을 넘어설때, 0 if(value<0) return 0; int& ret = cache[value]; if(ret!=-1) return ret; ret = 0; //점화식 for(int i=0;i<n;i++){ if(value-coin[i] >= 0) ret = ret + dp(value-coin[i]); } return ret; } int main(){ memset(cache,-1,sizeof(cache)); scanf("%d %d",&n,&k); for(int i=0;i<n;i++){ scanf("%d",&coin[i]); } printf("%d",dp(k)); }


밑은 각 동전별로 경우의 수를 구한 코드이다.


#include <cstdio>
int n,coin[101],k,cache[10001]={0,};
int main(){
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&coin[i]);
    }
    cache[0] = 1;
    
    //각 동전별로 값마다 경우의 수를 구한다.     
    for(int i = 0; i<n; i++){
        for(int j = 0; j<=k;j++){
            if(j>=coin[i])
                cache[j] += cache[j-coin[i]];
        }
    }   
    printf("%d",cache[k]);
}

코드가 훨씬 간결하고 직관적이다. DP에 대한 학습은 아직 더 필요한거같다.

'Algorithm > Problems' 카테고리의 다른 글

백준 - 1912 연속합  (0) 2016.03.07
백준 - 2294 동전 2  (0) 2016.03.07
백준 - 1697 숨바꼭질  (1) 2016.02.28
백준 - 1005 ACM Craft  (0) 2016.02.27
더블릿 - 댐  (0) 2016.02.26


문제 링크



BFS 문제다. 값의 범위만 조심하면 어려울 것 없는 문제였다.

다만 지금까지 풀었던 BFS는 방문을 체크하는 변수와 현재 탐색 레벨의 변수를 따로 두고 풀었는데, 이번에는 이전 문제와는 다르게,방문을 체크하는 변수 안에 현재 탐색 레벨을 담았다. 다만 그 체크를 위해 맨 처음 값이 1로 시작해야 했기에, 마지막 결과 값에서 1을 빼서 반환했다.

밑은 내가 풀이한 코드이다. 



#include <cstdio> #include <queue> using namespace std; //기존에 풀었던 BFS문제와는 다르게, visited 배열에 현재 레벨도 저장하였다. int n, k, visited[100001]={0,}; queue<int> q; int bfs(){ //큐에 수빈의 위치를 넣고, 방문을 체크하는 배열에 1을 넣어준다. q.push(n); visited[n] = 1; //bfs 시작 while(!q.empty()){ //큐를 꺼내고, 수빈이가 동생의 위치에 도달했는지 확인한다. int p = q.front(); q.pop(); if(p==k) return visited[p]-1; //수빈이 현재 위치 -1이 0보다 크거나 같고, 방문한 적이 없을경우. 현재 값에서 레벨을 1증가시켜 큐에 넣어준다. if(p-1>=0&&visited[p-1]==0){ visited[p-1] = visited[p]+1; q.push(p-1); } //수빈이 현재 위치의 +1이 100,000보다 작거나 같고, 방문한 적이 없을경우. if(p+1<=100000&&visited[p+1]==0){ visited[p+1] = visited[p]+1; q.push(p+1); } //수빈이 현재 위치의 2배가 0보다 크거나 같고, 방문한 적이 없을경우. if(2*p<=100000&&visited[2*p]==0){ visited[2*p] = visited[p]+1; q.push(2*p); } } } int main(){ scanf("%d %d",&n,&k); printf("%d",bfs()); }



'Algorithm > Problems' 카테고리의 다른 글

백준 - 2294 동전 2  (0) 2016.03.07
백준 - 2293 동전 1  (1) 2016.03.07
백준 - 1005 ACM Craft  (0) 2016.02.27
더블릿 - 댐  (0) 2016.02.26
알고스팟 - NQUEEN, 백준 - 9663 N-QUEEN  (1) 2016.02.25

+ Recent posts