[문제 링크]

 

1182번: 부분수열의 합

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

부분수열의 정의를 제대로 알고, 문제를 정확히 이해하면 쉽게 풀리는 문제라고 생각한다.

1~N개의 수를 포함하는 모든 조합들 중 순서만 다른 조합을 제외한 나머지 조합들을 대상으로 조합이 가진 원소들의 합이 입력된 값과 같다면 카운트를 1증가시키고 마지막으로 결과를 출력하면 원하는 답을 얻을 수 있다.

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> sequence;
int numCnt, stand, cnt=0;
void Solution(int start, int sum)
{
    for (int i = start; i < numCnt; i++)
        Solution(i + 1, sum+sequence[i]);
 
    if (start == 0 && sum == stand) return;    // stand가 0일 때 의도치않은 cnt값 증가 방지
    if (sum == stand) cnt++;
}
int main(void)
{
    cin >> numCnt >> stand;
    for (int i = 0; i < numCnt; i++)
    {
        int n;
        cin >> n;
        sequence.push_back(n);
    }
    Solution(0,0);
    cout << cnt << endl;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
 

알고리즘 200일 프로젝트 - 8day

내일도 열심히!

저작자표시

'알고리즘 > BOJ' 카테고리의 다른 글

백준 14889번: 스타트와 링크  (0) 2020.04.14
백준 1018번: 체스판 다시 칠하기  (0) 2020.04.13
백준 1966번: 프린터 큐  (0) 2020.04.13
백준 14888번: 연산자 끼워넣기  (0) 2020.04.12
백준 6603번: 로또  (0) 2020.04.12

[문제 링크]

 

1966번: 프린터 큐

문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를

www.acmicpc.net

문제의 취지에 맞게 queue 자료구조를 사용해서 풀었다.

큐는 맨 앞에 원소값만 참조할 수 있기때문에 임시 큐를 생성하여 전체 원소들과 비교하였다.

코드는 다음과 같이 진행된다.

맨 앞의 원소와 뒤에 원소들 비교 --> 더 큰 원소가 존재한다면 해당 원소를 맨 뒤로 보냄 --> 더 큰 원소가 존재하지 않을 때까지 반복 --> 찾고있는 원소 위치와 비교 --> 틀리다면 횟수 1증가, 앞에 원소 제거 --> 맞다면 횟수 출력

#include <iostream>
#include <queue>
using namespace std;
 
queue<int> wait;
int Solution(int find, int cnt)
{
    queue<int> temp = wait;
    int pick = temp.front();
    int len = temp.size();
    for (int i = 0; i < len; i++)
    {
        if (pick < temp.front())
        {
            wait.pop();
            wait.push(pick);
            if (find == 0) find = len - 1;
            else find--;
            return Solution(find, cnt);
        }
        else temp.pop();
    }
    cnt++;
    if(find != 0)
    {
        wait.pop();
        find--;
        return Solution(find, cnt);
    }
    else return cnt;
}
 
int main(void)
{
    int testcase;
    cin >> testcase;
    while (testcase--)
    {
        int imp, fd;
        cin >> imp >> fd;
        for (int i = 0; i < imp; i++)
        {
            int n;
            cin >> n;
            wait.push(n);
        }
        cout << Solution(fd, 0) << endl;
        while (!wait.empty()) wait.pop();
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

알고리즘 200일 프로젝트 - 8day

다른 사람들은 우선순위큐를 사용하여 쉽게 풀었는데, 나는 STL 사용법이 익숙치 않아서 무식하게 풀이한거 같다.

얼른 STL 공부해서 더 효율적인 방법으로 다시 한번 풀어보도록 해야겠다.

내일도 열심히!

저작자표시

'알고리즘 > BOJ' 카테고리의 다른 글

백준 1018번: 체스판 다시 칠하기  (0) 2020.04.13
백준 1182번: 부분수열의 합  (0) 2020.04.13
백준 14888번: 연산자 끼워넣기  (0) 2020.04.12
백준 6603번: 로또  (0) 2020.04.12
백준 7568번: 덩치  (0) 2020.04.11

[문제 링크]

 

14888번: 연산자 끼워넣기

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다. 

www.acmicpc.net

배열의 앞에있는 원소를 제거하고 새로운 원소를 배열의 맨 앞에 추가하기 위해 자료구조로 deque를 사용했다.

알고리즘은 간단하다. 앞에 두 원소에 대해 덧셈, 뺄셈, 곱셈, 연산을 수행한다음, 배열에서 앞에 두 원소를 빼내고 연산의 결과값을 배열 맨 앞에 추가한다.

ex) 1 2 3 4 5 -> 1+2=3 -> '3' 3 4 5-> 반복

원소 두개를 빼고 한개를 추가하기 때문에 작업이 이루어질때마다 배열의 원소 갯수는 한개씩 줄어들게 되고,

배열에 원소 갯수가 한개만 남게되면 모든 연산을 다 마쳤다는 뜻이므로 그 결과를 최댓값, 최솟값과 비교하여 저장한다. 그리고 이러한 작업을 4개 연산자로 할 수 있는 모든 경우의 수만큼 반복한다음 최댓값 최솟값을 출력해주면 원하는 답을 얻을 수 있다.

#include <iostream>
#include <vector>
#include <deque>
using namespace std;
 
deque<int> expr;
vector<int> oprt;    // oprt[0]: +, oprt[1]: -, oprt[2]: *, oprt[3]: /
const int MAX = -987654321;
const int MIN = 987654321;
 
int maximum = MAX;
int minimum = MIN;
int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }
 
int  _operator(int type)
{
    int res;
    switch (type)
    {
    case 0:
        res = expr[0] + expr[1];
        break;
    case 1:
        res = expr[0] - expr[1];
        break;
    case 2:
        res = expr[0] * expr[1];
        break;
    case 3:
        res = expr[0] / expr[1];
        break;
    }
    return res;
}
void Solution(deque<int>& expr, vector<int>& oprt)
{
    int len = expr.size();
    if (len == 1)    // 기저사례. expr에 원소가 한개라면 결과 출력
    {
        int result = expr[0];
        maximum = max(maximum, result);
        minimum = min(minimum, result);
        return;
    }
 
    for (int i = 0; i < 4; i++)
    {
        if (oprt[i] == 0) continue;
       oprt[i]--;
        int res = _operator(i);
        int expr0 = expr[0], expr1 = expr[1];
       expr.pop_front();
       expr.pop_front();
       expr.push_front(res);
       Solution(expr, oprt);
       expr.pop_front();
       expr.push_front(expr1);
       expr.push_front(expr0);
        oprt[i]++;
    }
}
int main(void)
{
    int num;
    cin >> num;
    for (int i = 0; i < num; i++)
    {
        int n;
        cin >> n;
        expr.push_back(n);
    }
    for (int i = 0; i < 4; i++)
    {
        int n;
        cin >> n;
        oprt.push_back(n);
    }
    Solution(expr, oprt);
    cout << maximum << endl;
    cout << minimum << endl;
 
    expr.clear();
    oprt.clear();
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
 

알고리즘 200일 프로젝트 - 7day

내일도 열심히! 

저작자표시

'알고리즘 > BOJ' 카테고리의 다른 글

백준 1182번: 부분수열의 합  (0) 2020.04.13
백준 1966번: 프린터 큐  (0) 2020.04.13
백준 6603번: 로또  (0) 2020.04.12
백준 7568번: 덩치  (0) 2020.04.11
백준 14502번: 연구소  (0) 2020.04.11

[문제 링크]

 

6603번: 로또

문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2

www.acmicpc.net

알고리즘은 다음의 순서로 진행된다.

1. 첫번째 수(k)와 k개의 숫자를 입력 받아 배열에 담는다 ( k==0 일 때 종료)

2. 입력받은 배열을 가지고 6개 숫자를 뽑는 조합을 사전 순으로 출력한다.

---> 단, 숫자를 오름차순으로 입력받으므로 별도의 정렬은 하지 않아도 된다.

---> 순서만 다른 숫자조합까지 출력하지 않도록 주의해야한다.

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> numArr;
vector<int> picked;
vector<bool> visited;
void Solution(vector<int>& picked,int toPick)
{
    if (toPick == 6)    // 기저사례. 6개 숫자 뽑았으면 출력
    {
        for (int i = 0; i < 6; i++)
            cout << picked[i] << ' ';
        cout << '\n';
        return;
    }
    int len = numArr.size();
    for (int i = 0; i < len; i++)
    {
        if (!picked.empty())
            if (picked.back() > numArr[i]) continue;    
        if (visited[i] == true) continue;
        visited[i] = true;
        picked.push_back(numArr[i]);
        Solution(picked, toPick + 1);
        visited[i] = false;
        picked.pop_back();
    }
}
int main(void)
{
    int num;
    while (1)
    {
        cin >> num;
        if (num == 0) break;
        for (int i = 0; i < num; i++)
        {
            int n;
            cin >> n;
            numArr.push_back(n);
            visited.push_back(false);
        }
        Solution(picked, 0);
        cout << '\n';
       numArr.clear();
       visited.clear();
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

알고리즘 200일 프로젝트 - 7day

내일도 열심히! 

저작자표시

'알고리즘 > BOJ' 카테고리의 다른 글

백준 1966번: 프린터 큐  (0) 2020.04.13
백준 14888번: 연산자 끼워넣기  (0) 2020.04.12
백준 7568번: 덩치  (0) 2020.04.11
백준 14502번: 연구소  (0) 2020.04.11
백준 2231번: 분해합  (0) 2020.04.11

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
vector<pair<int, int>> man;
vector<int> ranking;
int num;
 
void Solution(int toPick)
{
    if (toPick == num)    // 기저사례. num명의 등수를 다 계산했다면 등수를 출력한다
    {
        for (int i = 0; i < num; i++)
            cout << ranking[i] << ' ';
        return;
    }
 
    int cnt = 1;
    for (int i = 0; i < num; i++)
    {
        if (i == toPick) continue;    // 자기 자신과는 비교하지 않는다
        if (man[toPick].first < man[i].first && man[toPick].second < man[i].second) cnt++;
        // 자신보다 키와 몸무게가 더 큰 사람이 있다면 순위를 증가시킨다
    }
    ranking.push_back(cnt);
    Solution(toPick + 1);    // 등수 매긴 사람 수를 1 증가시키고 재귀호출
}
int main(void)
{
    cin >> num;
    for (int i = 0; i < num; i++)
    {
        int wi, hi;
        cin >> wi >> hi;
        man.push_back(pair<int, int>(wi, hi));
    }
    Solution(0);
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

알고리즘 200일 프로젝트 - 6day

간단하게 등수를 저장할 ranking이라는 벡터를 정의하고 ranking에 등수를 담아 출력하였다.

저작자표시

'알고리즘 > BOJ' 카테고리의 다른 글

백준 14888번: 연산자 끼워넣기  (0) 2020.04.12
백준 6603번: 로또  (0) 2020.04.12
백준 14502번: 연구소  (0) 2020.04.11
백준 2231번: 분해합  (0) 2020.04.11
백준 14501번: 퇴사  (0) 2020.04.10

여러가지 고려해야할 점이 많아서 복잡해 보이지만 결국은 조합을 구하는 완전탐색 문제이다.

주어진 배열에서 3개의 0을 1로 바꾸는 모든 경우의 수를 구한다. --> N개의 원소에서 3개를 뽑는 경우의 수와 같음

바뀐 배열에서 2의 상하좌우에 존재하는 0을 2로 바꿔주고, 이 작업을 더이상 바꿀 수 없을 때 까지 반복한 다음 배열에서 0의 갯수를 구하여 가장 큰 값을 결과로 반환해주면 된다.

#include <iostream>
#include <cstring>
using namespace std;
 
 
int col, row;
int board[9][9];
bool visited[9][9];
 
int max(int a, int b) { return a > b ? a : b; }
 
int Solution(int startY, int wall)
{
    if (wall == 3)            // 기저사례. 벽을 3개 쌓았다면 2를 다 퍼뜨리고 값을 반환한다.
    {
        int temp[9][9];
        for (int i = 0; i < col; i++)
            for (int j = 0; j < row; j++)
                temp[i][j] = board[i][j];
 
        bool state = false;
        while (state == false)
        {
            state = true;
            for (int i = 0; i < col; i++)
                for (int j = 0; j < row; j++)
                    if (temp[i][j] == 2)
                    {
                        if (i > 0)    // 2 의 9시 방향
                            if (temp[i - 1][j] == 0)
                            {
                                temp[i - 1][j] = 2;
                                state = false;
                            }
                        if (j > 0)    // 2의 12시 방향
                            if (temp[i][j - 1] == 0)
                            {
                                temp[i][j - 1] = 2;
                                state = false;
                            }
                        if (i + 1 < col)    // 2의 6시 방향
                            if (temp[i + 1][j] == 0)
                            {
                                temp[i + 1][j] = 2;
                                state = false;
                            }
                        if (j + 1 < row)    // 2의 3시 방향
                            if (temp[i][j + 1] == 0)
                            {
                                temp[i][j + 1] = 2;
                                state = false;
                            }
                    }
        }
        int cnt = 0;
        for (int i = 0; i < col; i++)
            for (int j = 0; j < row; j++)
                if (temp[i][j] == 0) cnt++;
        return cnt;
    }
 
    int ret = -1;
    for (int i = startY; i < col; i++)
    {
        for (int j = 0; j < row; j++)
        {
            if (board[i][j] == 0)
            {
                if (visited[i][j] == true) continue;
                visited[i][j] = true;
                board[i][j] = 1;
                ret = max(ret, Solution(i, wall + 1));
                board[i][j] = 0;
                visited[i][j] = false;
            }
        }
    }
    return ret;
}
 
int main(void)
{
    cin >> col >> row;
    memset(visited, false, sizeof(visited));    // 배열 전체를 방문하지 않은상태로 초기화
    for (int i = 0; i < col; i++)
    {
        for (int j = 0; j < row; j++)
        {
            int n;
            cin >> n;
            board[i][j] = n;
        }
    }
    cout << Solution(0,0) << endl;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

알고리즘 200일 프로젝트 - 6day

다른 사람들이 푼 방식을 보니 바이러스를 확산시키는데 DFS, BFS를 사용했다.

나는 아직 DFS와 BFS에 대해 잘 모르는 상태라 다소 무식하게 풀어낸거 같다.

그 부분들을 공부하게 되면 다시한번 풀어보도록 해야겠다.

저작자표시

'알고리즘 > BOJ' 카테고리의 다른 글

백준 6603번: 로또  (0) 2020.04.12
백준 7568번: 덩치  (0) 2020.04.11
백준 2231번: 분해합  (0) 2020.04.11
백준 14501번: 퇴사  (0) 2020.04.10
백준 2309번: 일곱 난쟁이  (0) 2020.04.10

 

 

1~N까지 완전탐색을 돌려도 시간 제한에 걸리지 않는 문제지만 생성자의 한가지 규칙을 발견하여 적용시켰다.

각 자리수는 0~9의 값만 가지기 때문에 각 자리수의 합은 최대 9 * N을 넘지 못한다.

ex) 99->9+9=18, 999->9+9+9=27

분해합 = 생성자+자리수이므로 생성자의 최솟값은 (분해합 - (9*N)) 인 것을 알 수 있다. 

#include <iostream>
using namespace std;
 
int Solution(int num)
{
    int temp = num;
    int cnt = 1;
    while ((temp /= 10) != 0)
        cnt++;
    int start = num - (cnt * 9);
    for (int i = start; i < num; i++)
    {
        temp = i;
        int sum = temp;
        while (temp / 10 != 0)
        {
            sum += temp % 10;
            temp /= 10;
        }
        sum += temp;
        if (sum == num)
        {
            return i;
        }
    }
    return 0;
}
int main(void)
{
    int num;
    cin >> num;
    cout << Solution(num) << endl;
 
    return 0;
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

 

 

 

알고리즘 200일 프로젝트 - 5day

내일도 열심히!

'알고리즘 > BOJ' 카테고리의 다른 글

백준 6603번: 로또  (0) 2020.04.12
백준 7568번: 덩치  (0) 2020.04.11
백준 14502번: 연구소  (0) 2020.04.11
백준 14501번: 퇴사  (0) 2020.04.10
백준 2309번: 일곱 난쟁이  (0) 2020.04.10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <vector>
using namespace std;
 
vector<int> time;
vector<int> pay;
int day;
int max(int a, int b) { return a > b ? a : b; }
int Solution(int start, int money)
{
    int ret = money;
    for (int i = start; i < day; i++)
    {
        int next = i + time[i];
        if (next > day) continue;
        ret = max(ret, Solution(next, money + pay[i]));   
    }
    return ret;
}
int main(void)
{
    cin >> day;
    for (int i = 0; i < day; i++)
    {
        int T, P;
        cin >> T >> P;
        time.push_back(T);
        pay.push_back(P);
    }
    cout << Solution(0,0) << endl;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

알고리즘 200일 프로젝트 - 5day

퇴사날이 0 <= day <= 15 라는 점을 이용하여 완전탐색으로 구현하는 간단한 문제였다.

저작자표시

'알고리즘 > BOJ' 카테고리의 다른 글

백준 6603번: 로또  (0) 2020.04.12
백준 7568번: 덩치  (0) 2020.04.11
백준 14502번: 연구소  (0) 2020.04.11
백준 2231번: 분해합  (0) 2020.04.11
백준 2309번: 일곱 난쟁이  (0) 2020.04.10

+ Recent posts

티스토리툴바