#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int solution(vector<int> money) 
{
    int dp1[1000010] = {0};
    int dp2[1000010] = {0};
    
    // 출발점 : 첫번째 집
    dp1[0] = money[0];
    dp1[1] = money[0];
    for(int i = 2; i < money.size()-1; i++)
    {
        dp1[i] = max(dp1[i-1], dp1[i-2] + money[i]);
    }
    
    // 출발점 : 두번째 집
    dp2[1] = money[1];
    for(int i = 2; i < money.size(); i++)
    {
        dp2[i] = max(dp2[i-1], dp2[i-2] + money[i]);
    }
    
    return max(dp1[money.size()-2], dp2[money.size()-1]);
}
cs
저작자표시

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

[프로그래머스 4] 징검다리 (C/C++) (★★★)  (0) 2020.04.26
[프로그래머스 4] 4단 고음 (C/C++) (★★★)  (0) 2020.03.11
[프로그래머스 4] 블록 게임 (C/C++) (★★)  (0) 2020.03.05
[프로그래머스 4] 카드게임 (C/C++) (★★)  (0) 2020.01.15
#include <string>
#include <vector>
using namespace std;
 
int solution(int m, int n, vector<vector<int>> puddles) 
{
    int dp[110][110] = {0}; // dp[n][m]
    
    // 세로 1로 표시
    for(int i = 1; i <= n; i++)
    {
        dp[i][1] = 1;
    }   
        
    // 가로 1로 표시
    for(int i = 1; i <= m; i++)
    {
        dp[1][i] = 1;
    }
    
    // 웅덩이 -1로 표시
    for(int i = 0; i < puddles.size(); i++)
    {
        dp[puddles[i][1]][puddles[i][0]] = -1;
    }
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            // 집
            if(i == 1 && j == 1)
            {
                continue;
            }
            
            // 웅덩이
            if(dp[i][j] == -1)
            {
                dp[i][j] = 0;
            }
            else
            {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;  
            }
        }
    }
    
    return dp[n][m];
}
cs
저작자표시

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

[프로그래머스 3] 입국 심사 (C/C++)  (0) 2020.01.27
[프로그래머스 3] 예산 (C/C++)  (0) 2020.01.26
[프로그래머스 3] 타일 장식물 (C/C++)  (0) 2020.01.11
[프로그래머스 3] 정수 삼각형 (C/C++)  (0) 2020.01.11
[프로그래머스 3] 저울 (C/C++) (★)  (0) 2020.01.11
#include <string>
#include <vector>
using namespace std;
 
long long solution(int N) 
{
    long long answer = 0;
    long long dp[85] = {0};
    
    dp[1] = 1;
    dp[2] = 1;
     
    if(N == 1)
    {
        return 1;
    }
    else if(N == 2)
    {
        return 6;
    }
    else
    {
        for(int i = 3; i <= N; i++)
        {
            dp[i] = dp[i-1] + dp[i-2];
        }
    }
    
    answer = dp[N]*2 + (dp[N]+dp[N-1])*2;
    
    return answer;
}
cs
저작자표시

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

[프로그래머스 3] 예산 (C/C++)  (0) 2020.01.26
[프로그래머스 3] 등굣길 (C/C++)  (0) 2020.01.14
[프로그래머스 3] 정수 삼각형 (C/C++)  (0) 2020.01.11
[프로그래머스 3] 저울 (C/C++) (★)  (0) 2020.01.11
[프로그래머스 3] 섬 연결하기 (C/C++) (★)  (0) 2020.01.10
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
 
int solution(vector<vector<int>> triangle) 
{
    int answer = 0;
    int Max[510][510] = {0};
    
    Max[0][0] = triangle[0][0];
    for(int i = 1; i < triangle.size(); i++)
    {
        for(int j = 0; j < triangle[i].size(); j++)
        {
            if(j == 0)
            {
                Max[i][j] = Max[i-1][j] + triangle[i][j];
            }
            else if(j == triangle[i].size()-1)
            {
                Max[i][j] = Max[i-1][triangle[i-1].size()-1] + triangle[i][j];
            }
            else
            {
                Max[i][j] = max(Max[i-1][j-1], Max[i-1][j]) + triangle[i][j];
            }
        }
    }
    
    for(int i = 0; i < triangle.size(); i++)
    {
        if(answer < Max[triangle.size()-1][i])
        {
            answer = Max[triangle.size()-1][i];
        }
    }
    
    return answer;
}
cs
저작자표시

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

[프로그래머스 3] 등굣길 (C/C++)  (0) 2020.01.14
[프로그래머스 3] 타일 장식물 (C/C++)  (0) 2020.01.11
[프로그래머스 3] 저울 (C/C++) (★)  (0) 2020.01.11
[프로그래머스 3] 섬 연결하기 (C/C++) (★)  (0) 2020.01.10
[프로그래머스 3] 단속카메라 (C/C++) (★)  (0) 2020.01.10
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int solution(vector<int> weight) 
{
    sort(weight.begin(), weight.end());
    
    if(weight[0] != 1)
    {
        return 1;
    }
    else
    {
        int sum = weight[0];
        
        for(int i = 1; i < weight.size(); i++)
        {
            // 다음수가 (누적합+1)이하면 만들수있음
            if(sum+1 < weight[i])
            {
                break;
            }
            else
            {
                sum += weight[i];
            }
        }
        
        return sum+1;
    }
}
cs
저작자표시

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

[프로그래머스 3] 타일 장식물 (C/C++)  (0) 2020.01.11
[프로그래머스 3] 정수 삼각형 (C/C++)  (0) 2020.01.11
[프로그래머스 3] 섬 연결하기 (C/C++) (★)  (0) 2020.01.10
[프로그래머스 3] 단속카메라 (C/C++) (★)  (0) 2020.01.10
[프로그래머스 3] 디스크 컨트롤러 (C/C++) (★★★)  (0) 2020.01.10
#include <string>
#include <vector>
#include <queue>
using namespace std;
 
vector<pair<int, int>> map[110];
int visited[110];
int answer;
 
// MST - 프림알고리즘
void prim(int start)
{
    visited[start] = 1;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    for(int i = 0; i < map[start].size(); i++)
    {
        int next = map[start][i].first;
        int nextCost = map[start][i].second;
        
        pq.push({nextCost, next});
    }
    
    while(!pq.empty())
    {
        int now = pq.top().second;
        int nowCost = pq.top().first;
        pq.pop();
        
        if(visited[now] == 1)
        {
            continue;
        }
        
        visited[now] = 1;
        answer += nowCost;
        
        for(int i = 0; i < map[now].size(); i++)
        {
            int next = map[now][i].first;
            int nextCost = map[now][i].second;
            
            pq.push({nextCost, next});
        }
    }
}
 
int solution(int n, vector<vector<int>> costs) 
{
    for(int i = 0; i < costs.size(); i++)
    {
        map[costs[i][0]].push_back({costs[i][1], costs[i][2]});
        map[costs[i][1]].push_back({costs[i][0], costs[i][2]});
    }
    
    prim(1);
    
    return answer;
}
cs
저작자표시

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

[프로그래머스 3] 정수 삼각형 (C/C++)  (0) 2020.01.11
[프로그래머스 3] 저울 (C/C++) (★)  (0) 2020.01.11
[프로그래머스 3] 단속카메라 (C/C++) (★)  (0) 2020.01.10
[프로그래머스 3] 디스크 컨트롤러 (C/C++) (★★★)  (0) 2020.01.10
[프로그래머스 3] 여행경로 (C/C++) (★)  (0) 2020.01.09
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
 
int solution(vector<vector<int>> routes) 
{
    int answer = 0;
    
    sort(routes.begin(), routes.end());
    
    int s, e;
    int cnt = 0;
    for(int i = 0; i < routes.size();)
    {
        int s = routes[i][0];
        int e = routes[i][1];
        int cnt = 0;
                
        for(int j = i; j < routes.size(); j++)
        {
            if(s <= routes[j][0] && routes[j][0] <= e)
            {
                s = routes[j][0];
                e = min(e, routes[j][1]);
                cnt++;
            }
            else
            {
                break;
            }
        }
        
        i += cnt;
        answer++;
    }
 
    return answer;
}
cs
저작자표시

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

[프로그래머스 3] 저울 (C/C++) (★)  (0) 2020.01.11
[프로그래머스 3] 섬 연결하기 (C/C++) (★)  (0) 2020.01.10
[프로그래머스 3] 디스크 컨트롤러 (C/C++) (★★★)  (0) 2020.01.10
[프로그래머스 3] 여행경로 (C/C++) (★)  (0) 2020.01.09
[프로그래머스 3] 단어 변환 (C/C++)  (0) 2020.01.09
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
 
int solution(vector<vector<int>> jobs) 
{   
    int answer = 0;
    
    vector<pair<int, int>> list;
    
    // 소요시간, 요청시간 순으로 삽입
    for(int i = 0; i < jobs.size(); i++)
    {
        list.push_back({jobs[i][1], jobs[i][0]});
    }
    
    // 작업 소요시간 순으로 정렬
    sort(list.begin(), list.end());
    
    int time = 0; // 현재시간
    while(list.size() > 0)
    {
        bool find = false;
        
        for(int i = 0; i < list.size();)
        {
            if(list[i].second <= time)
            {
                find = true;
                
                time += list[i].first;
                answer += time - list[i].second;
                
                list.erase(list.begin()+i);
                break;
            }
            else
            {
                i++;
            }
        }
        
        if(find == false)
        {
            time++;
        }
    }
    
    return answer / jobs.size();
}
cs
저작자표시

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

[프로그래머스 3] 섬 연결하기 (C/C++) (★)  (0) 2020.01.10
[프로그래머스 3] 단속카메라 (C/C++) (★)  (0) 2020.01.10
[프로그래머스 3] 여행경로 (C/C++) (★)  (0) 2020.01.09
[프로그래머스 3] 단어 변환 (C/C++)  (0) 2020.01.09
[프로그래머스 3] 네트워크 (C/C++)  (0) 2020.01.09

+ Recent posts

티스토리툴바