#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
 
int block[110][110][2];
int N;
 
int insert(int x, int y, int type)
{
    // 기둥
    if(type == 0)
    {
        // 기둥은 바닥 위에 있거나
        if(y == 0)
        {
            return 1;
        }
        // 보의 한쪽 끝 부분 위에 있거나 
        else if((x-1 >= 0 && block[x-1][y][1] == 1) || block[x][y][1] == 1)
        {
            return 1;
        }
        // 또는 다른 기둥 위에 있어야 합니다.
        else if(y-1 >= 0 && block[x][y-1][0] == 1)
        {
            return 1;
        }
        
        return 0;
    }
    // 보
    else
    {
        // 보는 한쪽 끝 부분이 기둥 위에 있거나
        if((y-1 >= 0 && block[x][y-1][0] == 1) || (x+1 <= N && y-1 >= 0 && block[x+1][y-1][0] == 1))
        {
            return 1;
        }   
        // 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
        else if(x-1 >= 0 && x+1 <= N && block[x-1][y][1] == 1 && block[x+1][y][1] == 1)
        {
            return 1;
        }
    
        return 0;   
    }
}
 
int erase()
{   
    for(int i = 0; i <= N; i++)
    {
        for(int j = 0; j <= N; j++)
        {
            for(int k = 0; k < 2; k++)
            {
                if(block[i][j][k] == 1)
                {
                    block[i][j][k] = 0;
                    
                    if(insert(i, j, k) == 0)
                    {
                        block[i][j][k] = 1;
                        return 0;
                    }
                    
                    block[i][j][k] = 1;
                }
            }
        }
    }
    
    return 1;
}
 
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) 
{
    vector<vector<int>> answer;
    N = n;
    
    for(int i = 0; i < build_frame.size(); i++)
    {
        int x = build_frame[i][0];
        int y = build_frame[i][1];
        
        // 기둥
        if(build_frame[i][2] == 0)
        {       
            // 설치
            if(build_frame[i][3] == 1)
            {
                // 성공
                if(insert(x, y, 0) == 1)
                {
                    block[x][y][0] = 1;
                }
            }
            // 삭제
            else
            {
                block[x][y][0] = 0;
                
                // 실패
                if(erase() == 0)
                {
                    block[x][y][0] = 1;
                }
            }
        }
        // 보
        else if(build_frame[i][2] == 1)
        {
            // 설치
            if(build_frame[i][3] == 1)
            {
                // 성공
                if(insert(x, y, 1) == 1)
                {
                    block[x][y][1] = 1;
                }
            }
            // 삭제
            else
            {
                block[x][y][1] = 0;
                
                // 실패
                if(erase() == 0)
                {
                    block[x][y][1] = 1;
                }
            }
        }
    }
    
    for(int i = 0; i <= n; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            for(int k = 0; k < 2; k++)
            {
                if(block[i][j][k] == 1)
                {
                    vector<int> temp;
                    temp.push_back(i);
                    temp.push_back(j);
                    temp.push_back(k);
                    
                    answer.push_back(temp);
                }
            }
        }
    }
    
    return answer;
}
cs
저작자표시 (새창열림)

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 배달 (C/C++)  (0) 2020.03.09
[프로그래머스 3] 자물쇠와 열쇠 (C/C++) (★★★)  (0) 2020.03.09
[프로그래머스 3] 거스름돈 (C/C++) (★)  (0) 2020.03.07
[프로그래머스 3] 보행자 천국 (C/C++)  (0) 2020.03.07
[프로그래머스 3] 가장 긴 팰린드롬 (C/C++) (★★)  (0) 2020.03.07
#include <iostream>
#include <algorithm>
using namespace std;
 
int main(void)
{
//    freopen("B2294_input.txt", "r", stdin);
    
    int n, k;
    int dp[10010] = {0};
    int coin[10010];
    
    cin >> n >> k;
    
    for(int i = 0; i < n; i++)
    {
        cin >> coin[i]; 
    }
    
    for(int i = 0; i <= k; i++)
    {
        dp[i] = 99999999;
    }
    dp[0] = 0;
    
    for(int i = 0; i < n; i++)
    {
        for(int j = coin[i]; j <= k; j++)
        {
            dp[j] = min(dp[j], dp[j-coin[i]] + 1);
        }
    }
    
    if(dp[k] == 99999999)
    {
        cout << "-1";
    }
    else
    {
        cout << dp[k];    
    }
    
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > DP' 카테고리의 다른 글

[백준 1480] 보석 모으기 (DP, Bitmask) (C/C++) (★★★)  (0) 2020.03.13
[백준 2098] 외판원 순회 (DP, Bitmask) (C/C++) (★★★)  (0) 2020.03.12
[백준 2293] 동전 1 (DP) (C/C++) (★★)  (0) 2020.03.07
[백준 11052] 카드 구매하기 (DP) (C/C++)  (0) 2020.01.22
[백준 2011] 암호코드 (DP) (C/C++) (★)  (0) 2020.01.22
#include <iostream>
#include <algorithm>
using namespace std;
 
int main(void)
{
//    freopen("B2293_input.txt", "r", stdin);
    
    int n, k;
    long long dp[10010] = {0};
    int coin[10010];
        
    cin >> n >> k;
    
    for(int i = 0; i < n; i++)
    {
        cin >> coin[i];
    }
 
    dp[0] = 1;
    
    for(int i = 0; i < n; i++)
    {
        for(int j = coin[i]; j <= k; j++)
        {
            dp[j] = dp[j] + dp[j-coin[i]];
        }
    }
    
    cout << dp[k];
    
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > DP' 카테고리의 다른 글

[백준 2098] 외판원 순회 (DP, Bitmask) (C/C++) (★★★)  (0) 2020.03.12
[백준 2294] 동전 2 (DP) (C/C++) (★★)  (0) 2020.03.07
[백준 11052] 카드 구매하기 (DP) (C/C++)  (0) 2020.01.22
[백준 2011] 암호코드 (DP) (C/C++) (★)  (0) 2020.01.22
[백준 9461] 파도반 수열(DP) (C/C++)  (0) 2020.01.22
#include <iostream>
#include <algorithm>
using namespace std;
 
int main(void)
{
//    freopen("B11047_input.txt", "r", stdin);
    
    int N, sum;
    int coin[10];
    int ans = 0;
    
    cin >> N >> sum;
    
    for(int i = 0; i < N; i++)
    {
        cin >> coin[i];
    }
    
    sort(coin, coin+N, greater<int>());
 
    int coinIdx = 0;
    while(sum > 0)
    {
        if(sum >= coin[coinIdx])
        {
            sum -= coin[coinIdx];
            ans++;
        }
        else
        {
            coinIdx++;
        }
    }
    
    cout << ans;
    
    return 0;
}
cs
저작자표시 (새창열림)

'Baekjoon > Greedy' 카테고리의 다른 글

[백준 1343] 폴리오미노 (Greedy) (C/C++)  (0) 2019.12.30
#include <string>
#include <vector>
using namespace std;
 
int solution(int n, vector<int> money) 
{
    long long dp[100010] = {0};
    dp[0] = 1;
    
    for(int i = 0; i < money.size(); i++)
    {
        for(int j = money[i]; j <= n; j++)
        {
            dp[j] = (dp[j] + dp[j-money[i]]) % 1000000007;                                         
        }
    }
    
    return dp[n];
}
cs
저작자표시 (새창열림)

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 자물쇠와 열쇠 (C/C++) (★★★)  (0) 2020.03.09
[프로그래머스 3] 기둥과 보 (C/C++) (★★★)  (0) 2020.03.08
[프로그래머스 3] 보행자 천국 (C/C++)  (0) 2020.03.07
[프로그래머스 3] 가장 긴 팰린드롬 (C/C++) (★★)  (0) 2020.03.07
[프로그래머스 3] 종이접기 (C/C++) (★)  (0) 2020.03.06
#include <vector>
using namespace std;
 
int MOD = 20170805;
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int m, int n, vector<vector<int>> city_map) 
{
    int answer = 0;
    int dp[510][510][2] = {0}; // 0 왼쪽, 1 위쪽
    int row = city_map.size();
    int col = city_map[0].size();
    
    for(int i = 0; i < row; i++)
    {
        if(city_map[i][0] == 1)
        {
            break;
        }
        
        dp[i][0][1] = 1;
    }
    
    for(int i = 0; i < col; i++)
    {
        if(city_map[0][i] == 1)
        {
            break;
        }
        
        dp[0][i][0] = 1;
    }
    
    for(int i = 1; i < row; i++)
    {
        for(int j = 1; j < col; j++)
        {
            if(city_map[i-1][j] == 0)
            {
                dp[i][j][1] += (dp[i-1][j][0] + dp[i-1][j][1]) % MOD;
            }
            else if(city_map[i-1][j] == 2)
            {
                dp[i][j][1] += (dp[i-1][j][1] % MOD);
            }
            
            if(city_map[i][j-1] == 0)
            {
                dp[i][j][0] += (dp[i][j-1][0] + dp[i][j-1][1]) % MOD;
            }
            else if(city_map[i][j-1] == 2)
            {
                dp[i][j][0] += (dp[i][j-1][0] % MOD);
            }
        }
    }
    
    return (dp[row-1][col-1][0] + dp[row-1][col-1][1]) % MOD;
}
cs
저작자표시 (새창열림)

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 기둥과 보 (C/C++) (★★★)  (0) 2020.03.08
[프로그래머스 3] 거스름돈 (C/C++) (★)  (0) 2020.03.07
[프로그래머스 3] 가장 긴 팰린드롬 (C/C++) (★★)  (0) 2020.03.07
[프로그래머스 3] 종이접기 (C/C++) (★)  (0) 2020.03.06
[프로그래머스 3] 2xN 타일링 (C/C++)  (0) 2020.03.06
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int solution(string s)
{
    int dp[2510][2510] = {0};
    int Max;
    
    // 길이 1
    for(int i = 0; i < s.size(); i++)
    {
        dp[i][i] = 1;
        Max = 1;
    }
    
    // 길이 2
    for(int i = 0; i < s.size()-1; i++)
    {
        if(s[i] == s[i+1])
        {
            dp[i][i+1] = 1;
            Max = 2;
        }
    }
    
    // 길이 3 이상
    for(int k = 2; k < s.size(); k++)
    {
        for(int i = 0; i <= s.size()-1-k; i++)
        {
            int j = i + k;
            
            if(s[i] == s[j] && dp[i+1][j-1] == 1)
            {
                dp[i][j] = 1;
                
                if(Max < k+1)
                {
                    Max = k+1;
                }
            }
        }
    }
 
    return Max;
}
 cs
저작자표시 (새창열림)

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 거스름돈 (C/C++) (★)  (0) 2020.03.07
[프로그래머스 3] 보행자 천국 (C/C++)  (0) 2020.03.07
[프로그래머스 3] 종이접기 (C/C++) (★)  (0) 2020.03.06
[프로그래머스 3] 2xN 타일링 (C/C++)  (0) 2020.03.06
[프로그래머스 3] 길찾기 게임 (C/C++) (★★)  (0) 2020.03.05
#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
vector<int> solution(int n) 
{
    vector<int> answer;
    string paper = "0";
    
    for(int i = 1; i < n; i++)
    {
        string temp_paper = paper;
 
        // 원래 종이의 가운데 부분만 다른 숫자로 변경
        if(temp_paper[temp_paper.size()/2] == '0')
        {
            temp_paper[temp_paper.size()/2] = '1';
        }
        else
        {
            temp_paper[temp_paper.size()/2] = '0';
        }
 
        // 0 더하고, 가운데 부분만 변경한 종이를 이어붙이면 되는 규칙
        paper += "0";
        paper += temp_paper;
    }
        
    for(int i = 0; i < paper.size(); i++)
    {
        answer.push_back(paper[i]-'0');
    }
 
    return answer;
}
cs
저작자표시 (새창열림)

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 보행자 천국 (C/C++)  (0) 2020.03.07
[프로그래머스 3] 가장 긴 팰린드롬 (C/C++) (★★)  (0) 2020.03.07
[프로그래머스 3] 2xN 타일링 (C/C++)  (0) 2020.03.06
[프로그래머스 3] 길찾기 게임 (C/C++) (★★)  (0) 2020.03.05
[프로그래머스 3] 매칭 점수 (C/C++)  (0) 2020.03.01

+ Recent posts

티스토리툴바