'알고리즘/BOJ' 카테고리의 글 목록 (24 Page)

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

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
35
36
37
38
39

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> picked;
vector<int> smallMan;
bool finish = true;
void findSmallMan(vector<int>& picked, int start ,int tallSum)
{
    if (finish == false) return;    // 기저사례. 이미 1번 출력했다면 함수를 빠져나온다.
    if (picked.size() == 7)
    {
        if (tallSum == 100)
        {
            sort(picked.begin(), picked.end());
            for (int i = 0; i < 7; i++)
                cout << picked[i] << endl;
            finish = false;
        }
    }
    for (int i = start; i < 9; i++)    // 순서만 다른 조합을 배제하기 위해 start부터 시작
    {
        picked.push_back(smallMan[i]);
        findSmallMan(picked, i + 1, tallSum + smallMan[i]);
        picked.pop_back();
    }
}
int main(void)
{
    for (int i = 0; i < 9; i++)
    {
        int tall;
        cin >> tall;
        smallMan.push_back(tall);
    }
    findSmallMan(picked, 0, 0);
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter

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

원소의 수가 9개로 제한되어 있기때문에 완전탐색 알고리즘을 적용하여 간단하게 해결할 수 있는 문제였다.

저작자표시

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

백준 6603번: 로또 (0)	2020.04.12
백준 7568번: 덩치 (0)	2020.04.11
백준 14502번: 연구소 (0)	2020.04.11
백준 2231번: 분해합 (0)	2020.04.11
백준 14501번: 퇴사 (0)	2020.04.10

언제나 처음처럼