#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
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;
 
vector<string> answer;
vector<pair<string, string>> new_tickets;
map<int, int> visited;
bool flag = false;
 
int check()
{
    for(int i = 0; i < new_tickets.size(); i++)
    {
        if(visited[i] == 0)
        {
            return 0;
        }
    }
    
    return 1;
}
 
void DFS(string start)
{
    if(check() == 1)
    {
        flag = true;
        return;
    }
    
    for(int i = 0; i < new_tickets.size(); i++)
    {
        if(new_tickets[i].first == start && visited[i] == 0)
        {
            visited[i] = 1;
            answer.push_back(new_tickets[i].second);
            DFS(new_tickets[i].second);
            if(flag == true)
            {
                return;
            }
            answer.pop_back();
            visited[i] = 0;
        }
    }
}
 
vector<string> solution(vector<vector<string>> tickets) 
{
    for(int i = 0; i < tickets.size(); i++)
    {
        new_tickets.push_back({tickets[i][0], tickets[i][1]});
    }
    
    // 사전정렬을 위한 오름차순정렬
    sort(new_tickets.begin(), new_tickets.end());
    
    for(int i = 0; i < new_tickets.size(); i++)
    {
        if(new_tickets[i].first == "ICN")
        {
            answer.push_back(new_tickets[i].first);
            DFS(new_tickets[i].first);
            if(flag == true)
            {
                return answer;
            }
            answer.pop_back();
        }  
    }
}
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.08
#include <string>
#include <vector>
#include <queue>
#include <map>
using namespace std;
 
vector<string> copy_words;
string copy_target;
 
queue<string> q;
map<string, int> visited;
 
int check(string word, string next)
{
    int cnt = 0;
    
    for(int i = 0; i < word.size(); i++)
    {
        if(word[i] != next[i])
        {
            cnt++;
        }
    }
    
    if(cnt == 1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void BFS(string begin)
{
    visited[begin] = 1;
    q.push(begin);
    
    while(!q.empty())
    {
        string word = q.front();
        q.pop();
        
        if(word == copy_target)
        {
            return;
        }
        
        for(int i = 0; i < copy_words.size(); i++)
        {
            if(check(word, copy_words[i]) == 1 && visited[copy_words[i]] == 0)
            {
                visited[copy_words[i]] = visited[word] + 1;
                q.push(copy_words[i]);
            }         
        }     
    } 
}
 
int solution(string begin, string target, vector<string> words)
{
    copy_words = words;
    copy_target = target;
    
    BFS(begin);
    
    if(visited[target] == 0)
    {
        return 0;
    }
    else
    {
        return visited[target]-1;   
    }
}
cs
저작자표시

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

[프로그래머스 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.08
[프로그래머스 3] 베스트 앨범 (C/C++) (★)  (0) 2020.01.07

+ Recent posts

티스토리툴바