#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int cal(vector<int> rocks, int mid, int distance)
{
    int cnt = 0;
    int prev = 0;
    
    for(int i = 0; i < rocks.size(); i++)
    {
        if(rocks[i] - prev < mid)
        {
            cnt++;
        }
        else
        {
            prev = rocks[i];
        }
    }
    
    // 도착지점과 마지막 돌 체크
    if(distance - prev < mid)
    {
        cnt++;
    }
    
    return cnt;
}
 
int solution(int distance, vector<int> rocks, int n) 
{
    int Max = 0;
    int left = 1;
    int right = distance;
    
    sort(rocks.begin(), rocks.end());
    
    while(left <= right)
    {
        // 바위 사이 거리의 최솟값
        int mid = (left + right) / 2;
        
        if(cal(rocks, mid, distance) > n)
        {
            right = mid-1;
        }
        else
        {
            left = mid+1;
            
            if(mid > Max)
            {
                Max = mid;
            }
        }
    }
    
    return Max;
}
cs
저작자표시

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

[프로그래머스 4] 4단 고음 (C/C++) (★★★)  (0) 2020.03.11
[프로그래머스 4] 블록 게임 (C/C++) (★★)  (0) 2020.03.05
[프로그래머스 4] 카드게임 (C/C++) (★★)  (0) 2020.01.15
[프로그래머스 4] 도둑질 (C/C++) (★)  (0) 2020.01.15
#include <iostream>
#include <math.h>
using namespace std;
 
int max_mul;
 
int count_mul(int n)
{
    return log(n) / log(3);
}
 
int solve(int add, int mul, int n)
{
    int result = 0;
    
    // '*'의 최대 갯수보다 '+'의 갯수가 많아지면 종료
    if(2 * max_mul < add)
    {
        return 0;
    }
    
    if(n == 1)
    {
        return 1;
    }
    
    if(n % 3 == 0)
    {
        if(2 * (mul + 1) <= add)
        {
            result += solve(add, mul + 1, n / 3);    
        }
  
        result += solve(add + 3, mul, n - 3);
    }
    else if(n % 3 != 0)
    {
        result += solve(add + (n % 3), mul, n - (n % 3));
    }
    
    return result;
}
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n) 
{
    int answer = 0;
    
    max_mul = count_mul(n);
    answer = solve(0, 0, n);
    
    return answer;
}
cs
저작자표시

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

[프로그래머스 4] 징검다리 (C/C++) (★★★)  (0) 2020.04.26
[프로그래머스 4] 블록 게임 (C/C++) (★★)  (0) 2020.03.05
[프로그래머스 4] 카드게임 (C/C++) (★★)  (0) 2020.01.15
[프로그래머스 4] 도둑질 (C/C++) (★)  (0) 2020.01.15
#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
int row, col;
int blockCnt;
int black = -1;
int boomCnt;
vector<vector<int>> copy_board(55, vector<int>(55));
 
void copy(vector<vector<int>> &to, vector<vector<int>> &from)
{
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            to[i][j] = from[i][j];
        }
    }
}
 
int isSquare(int x, int y, int shape, int color, vector<vector<int>> &board) // shape(0): 2*3 , shape(1): 3*2
{
    int colorCnt = 0;
    int blackCnt = 0;
    
    if(shape == 0)
    {
        for(int i = x; i <= x+1; i++)
        {
            for(int j = y; j <= y+2; j++)
            {
                if(board[i][j] == color)
                {
                    colorCnt++;
                }
                else if(board[i][j] == black)
                {
                    blackCnt++;
                }
            }
        }
    }
    else
    {
        for(int i = x; i <= x+2; i++)
        {
            for(int j = y; j <= y+1; j++)
            {
                if(board[i][j] == color)
                {
                    colorCnt++;
                }
                else if(board[i][j] == black)
                {
                    blackCnt++;
                }
            }
        }
    }
    
    if(colorCnt == 4 && blackCnt == 2)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void print(vector<vector<int>> &board)
{
    for(int i = 0; i < col; i++)
    {
        for(int j = 0; j < row; j++)
        {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
 
void bomb(int x, int y, int shape, vector<vector<int>> &board)
{
    if(shape == 0)
    {
        for(int i = x; i <= x+1; i++)
        {
            for(int j = y; j <= y+2; j++)
            {
                board[i][j] = 0;
                copy_board[i][j] = 0;
            }
        }
    }
    else
    {
        for(int i = x; i <= x+2; i++)
        {
            for(int j = y; j <= y+1; j++)
            {
                board[i][j] = 0;
                copy_board[i][j] = 0;
            }
        }
    }   
}
 
bool fall(vector<vector<int>> &board)
{
    bool boomCheck = false;
    copy(copy_board, board);
    
    // 검은 블록 떨어뜨리기
    for(int i = 0; i < col; i++)
    {    
        for(int j = 0; j < row; j++)
        {   
            if(board[j][i] != 0)
            {
                break;
            }
            
            board[j][i] = black;
         }
    }
    
    // print(board);
    
    for(int i = 1; i <= blockCnt; i++)
    {
        // 2*3 모양
        for(int j = 0; j <= row-2; j++)
        {
            for(int k = 0; k <= col-3; k++)
            {
                if(isSquare(j, k, 0, i, board))
                {
                    boomCheck = true;
                    bomb(j, k, 0, board);
                    boomCnt++;
                }
            }
        }
        
        // 3*2 모양
        for(int j = 0; j <= row-3; j++)
        {
            for(int k = 0; k <= col-2; k++)
            {
                if(isSquare(j, k, 1, i, board))
                {
                    boomCheck = true;
                    bomb(j, k, 1, board);
                    boomCnt++;
                }
            }
        }
    }
    
    copy(board, copy_board);
    
    // print(board);
    
    return boomCheck;
}
 
int solution(vector<vector<int>> board) 
{
    row = board.size();
    col = row;
      
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(board[i][j] > blockCnt)
            {
                blockCnt = board[i][j];
            }
        }
    }
    
    while(1)
    {
        bool check = fall(board);
        
        if(check == false)
        {
            break;
        }
    }       
    
    return boomCnt;
}
cs
저작자표시

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

[프로그래머스 4] 징검다리 (C/C++) (★★★)  (0) 2020.04.26
[프로그래머스 4] 4단 고음 (C/C++) (★★★)  (0) 2020.03.11
[프로그래머스 4] 카드게임 (C/C++) (★★)  (0) 2020.01.15
[프로그래머스 4] 도둑질 (C/C++) (★)  (0) 2020.01.15
#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
 
vector<int> a; // left
vector<int> b; // right
int dp[2010][2010] = {0};
 
int solve(int leftIdx, int rightIdx)
{
    if(leftIdx == a.size() || rightIdx == b.size())
    {
        return 0;
    }
    
    if(dp[leftIdx][rightIdx] != -1)
    {
        return dp[leftIdx][rightIdx];
    }
    
    // 1. 언제든지 왼쪽 카드만 통에 버릴 수도 있고 왼쪽 카드와 오른쪽 카드를 둘 다 통에 버릴 수도 있다. 이때 얻는 점수는 없다.
    dp[leftIdx][rightIdx] = max(solve(leftIdx+1, rightIdx), solve(leftIdx+1, rightIdx+1));
    
    // 2. 오른쪽 카드에 적힌 수가 왼쪽 카드에 적힌 수보다 작은 경우에는 오른쪽 카드만 통에 버릴 수도 있다. 오른쪽 카드만 버리는 경우에는 오른쪽 카드에 적힌 수만큼 점수를 얻는다.
    if(a[leftIdx] > b[rightIdx])
    {
        dp[leftIdx][rightIdx] = max(dp[leftIdx][rightIdx], solve(leftIdx, rightIdx+1) + b[rightIdx]);
    }
    
    return dp[leftIdx][rightIdx];
}
 
int solution(vector<int> left, vector<int> right) 
{
    a = left;
    b = right;
    
    memset(dp, -1, sizeof(dp));
    
    int answer = solve(0, 0); 
    
    return answer;
}
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>
#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

+ Recent posts

티스토리툴바