#include <string>
#include <vector>
using namespace std;
 
long long dp[2010];
 
long long solve(int n)
{
    if(n == 0)
    {
        return 1;
    }
    else if(n < 0)
    {
        return 0;
    }
    
    if(dp[n] != 0)
    {
        return dp[n];
    }
    
    dp[n] = (solve(n-1) + solve(n-2)) % 1234567;
 
    return dp[n] % 1234567;
}
 
long long solution(int n) 
{
    long long answer = solve(n);
    
    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.09
[프로그래머스 3] 최고의 집합 (C/C++)  (0) 2020.03.09
[프로그래머스 3] 배달 (C/C++)  (0) 2020.03.09
#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
 
long long solution(int n, vector<int> works) 
{
    long long answer = 0;
    
    priority_queue<int> pq;
    
    for(int i = 0; i < works.size(); i++)
    {
        pq.push(works[i]);
    }
    
    for(int i = 1; i <= n; i++)
    {
        int value = pq.top();
        pq.pop();
        
        if(value == 0)
        {
            break;
        }
        
        value--;
        pq.push(value);
    }
    
    for(int i = 0; i < works.size(); i++)
    {
        long long value = pq.top();
        pq.pop();
        
        answer += value * value;
    }
    
    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.09
[프로그래머스 3] 배달 (C/C++)  (0) 2020.03.09
[프로그래머스 3] 자물쇠와 열쇠 (C/C++) (★★★)  (0) 2020.03.09
#include <string>
#include <vector>
using namespace std;
 
vector<int> solution(int n, int s) 
{
    vector<int> answer;
    
    if(n > s)
    {
        answer.push_back(-1);
        
        return answer;
    }
    else
    {
        if(s % n == 0)
        {
            int element = s / n;
            
            for(int i = 1; i <= n; i++)
            {
                answer.push_back(element);
            }
        }
        else
        {
            // 반복횟수
            int cnt = s % n;
            
            // 나머지를 가지고 1씩 분배해서 나눠가지면 최대 곱
            int element = s / n + 1;
            
            for(int i = 1; i <= n-cnt; i++)
            {
                answer.push_back(element-1);
            }
            
            for(int i = 1; i <= cnt; i++) 
            {
                answer.push_back(element);
            }
        }
        
        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.09
[프로그래머스 3] 자물쇠와 열쇠 (C/C++) (★★★)  (0) 2020.03.09
[프로그래머스 3] 기둥과 보 (C/C++) (★★★)  (0) 2020.03.08
#include <iostream>
#include <vector>
using namespace std;
 
int d[55][55];
 
void floyd(int N)
{
    for(int k = 1; k <= N; k++)
    {
        for(int i = 1; i <= N; i++)
        {
            for(int j = 1; j <= N; j++)
            {
                if(d[i][k] + d[k][j] < d[i][j])
                {
                    if(i == j)
                    {
                        continue;
                    }
                    
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
    
}
 
int solution(int N, vector<vector<int>> road, int K) 
{
    int answer = 0;
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            if(i == j)
            {
                d[i][j] = 0;
            }
            else
            {
                d[i][j] = 99999999;   
            }
        }
    }
 
    for(int i = 0; i < road.size(); i++)
    {
        // 전에 나온 도로 -> 최소면 갱신
        if(d[road[i][0]][road[i][1]] != 99999999)
        {
            if(road[i][2] < d[road[i][0]][road[i][1]])
            {
                d[road[i][0]][road[i][1]] = road[i][2];
                d[road[i][1]][road[i][0]] = road[i][2];
            }
        }
        // 처음 나온 도로 -> 바로 갱신
        else
        {
            d[road[i][0]][road[i][1]] = road[i][2];
            d[road[i][1]][road[i][0]] = road[i][2];
        }
    }
    
    floyd(N);
    
    for(int i = 1; i <= N; i++)
    {
        if(d[1][i] <= K)
        {
            answer++;
        }
    }
 
    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.09
[프로그래머스 3] 기둥과 보 (C/C++) (★★★)  (0) 2020.03.08
[프로그래머스 3] 거스름돈 (C/C++) (★)  (0) 2020.03.07
#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
void rotate(vector<vector<int>> &key)
{
    vector<vector<int>> temp = key;
    
    for(int i = 0; i < key.size(); i++)
    {
        for(int j = 0; j < key.size(); j++)
        {
             temp[i][j] = key[j][key.size()-1-i];
        }
    }
    
    key = temp;
}
 
bool solution(vector<vector<int>> key, vector<vector<int>> lock) 
{
    int m = key.size();
    int n = lock.size();
    int hom = 0;
    
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(lock[i][j] == 0)
            {
                hom++;
            }
        }
    }
    
    for(int r = 1; r <= 4; r++)
    {   
        for(int i = -n; i <= n; i++)
        {
            for(int j = -n; j <= n; j++)
            {
                bool fail = true;
                int cnt = 0;
 
                for(int x = 0; x < m; x++)
                {
                    for(int y = 0; y < m; y++)
                    {       
                        int nx = i + x;
                        int ny = j + y;
                        
                        if(0 <= nx && nx < n && 0 <= ny && ny < n) 
                        {
                            //  열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며
                            if(lock[nx][ny] == 0 && key[x][y] == 1)
                            {
                                cnt++;
                            }
                            // 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다.
                            else if(lock[nx][ny] == 1 && key[x][y] == 1)
                            {
                                fail = false;
                            }
                        }
                    }
                }
                
                if(hom == cnt && fail == true)
                {
                    return true;
                }
            }
        }
        
        rotate(key);
    }
    
    return false;
}
cs
저작자표시

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

[프로그래머스 3] 최고의 집합 (C/C++)  (0) 2020.03.09
[프로그래머스 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
#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 <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

+ Recent posts

티스토리툴바