'알고리즘/백준' 카테고리의 글 목록

https://www.acmicpc.net/problem/15235

During the Olympiad finals we usually serve pizza for the contestants. When the food arrives, the contestants to queue to get some pizza. Each student will be given a single slice of pizza when his/her turn arrives. The problem is that some people need more than one slice of pizza to be well fed so they need to queue again for more pizza after they get the first one.
Given a list of slices needed to fed each of the contestants, compute how long it will take to fed all of them. We can give a slice of pizza every second and when a contestant is well fed he does not return to the queue.

code >>

#include <iostream>
#include<queue>
#include<vector>
int main()
{
    std::ios::ios_base::sync_with_stdio(false);
    int N = 0;
    std::cin >> N;
    std::vector<int> count(N);
    std::queue<int> q;
    for (int i= 0; i < N; ++i)
    {
        std::cin >> count[i];
        q.push(i);
    }
    std::vector<int> answer(N, 0);
    int time = 0;
    while (!q.empty())
    {
        int value = q.front();
        q.pop();
        time++;
        answer[value] = time;
        count[value]--;
        if (count[value] > 0)
        {
            q.push(value);
        }
    }
    for (int i = 0; i < N; i++)
    {
        std::cout << answer[i] << " ";
    }
    std::cout << "\n";
}

저작자표시 비영리

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

1766>문제집 (0)	2019.03.12
1654>랜선 자르기 (0)	2019.02.18
1010>다리놓기 (0)	2018.12.17
11657>타임머신 (0)	2018.12.04
1786>찾기 (0)	2018.11.26

https://www.acmicpc.net/problem/1766

민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다.

어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다.

N개의 문제는 모두 풀어야 한다.

먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.

가능하면 쉬운 문제부터 풀어야 한다.

예를 들어서 네 개의 문제가 있다고 하자. 4번 문제는 2번 문제보다 먼저 푸는 것이 좋고, 3번 문제는 1번 문제보다 먼저 푸는 것이 좋다고 하자. 만일 4-3-2-1의 순서로 문제를 풀게 되면 조건 1과 조건 2를 만족한다. 하지만 조건 3을 만족하지 않는다. 4보다 3을 충분히 먼저 풀 수 있기 때문이다. 따라서 조건 3을 만족하는 문제를 풀 순서는 3-1-4-2가 된다.

문제의 개수와 먼저 푸는 것이 좋은 문제에 대한 정보가 주어졌을 때, 주어진 조건을 만족하면서 민오가 풀 문제의 순서를 결정해 주는 프로그램을 작성하시오.

code>>

#include <iostream>

#include <vector>

#include <queue>

std::vector<int> input[32001];

int vertext[32001];

int main()

{

std::ios::ios_base::sync_with_stdio(false);

int N, M, in1, in2;

std::cin >> N >> M;

for (int i = 0; i < M; ++i)

{

std::cin >> in1 >> in2;

vertext[in2]++;

input[in1].push_back(in2);

}

std::priority_queue<int> q;

for (int i = 1; i <= N; ++i)

{

if (vertext[i] == 0)

q.push(-i);

}

while (!q.empty())

{

auto idx = -q.top();

q.pop();

printf("%d ", idx);

for (int i = 0; i < input[idx].size(); ++i)

{

vertext[input[idx][i]]--;

if (vertext[input[idx][i]] == 0)

q.push(-input[idx][i]);

}

printf("\n");

return 0;

}

저작자표시 비영리

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

15235>Olympiad Pizza (0)	2024.02.18
1654>랜선 자르기 (0)	2019.02.18
1010>다리놓기 (0)	2018.12.17
11657>타임머신 (0)	2018.12.04
1786>찾기 (0)	2018.11.26

https://www.acmicpc.net/problem/1654

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm 은 버려야 한다.(이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

code >>

#include<iostream>

#include<algorithm>

long long inputs[10001];

int main()

{

std::ios::ios_base::sync_with_stdio(false);

int K, N;

std::cin >> K >> N;

for (int i = 0; i < K; ++i)

std::cin>>inputs[i];

std::sort(inputs, inputs + K, std::greater<long long>());

long long left = 1, ans = 0;

long long right = inputs[0];

while (left <= right)

{

long long mid = (left + right) / 2;

long long sum = 0;

for (int i = 0; i < K; i++)

sum += inputs[i] / mid;

if (sum >= N)

{

left = mid + 1;

if(ans < mid)

ans = mid;

}

else

{

right = mid - 1;

}

printf("%lld\n", ans);

return 0;

}

저작자표시 비영리

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

15235>Olympiad Pizza (0)	2024.02.18
1766>문제집 (0)	2019.03.12
1010>다리놓기 (0)	2018.12.17
11657>타임머신 (0)	2018.12.04
1786>찾기 (0)	2018.11.26

https://www.acmicpc.net/problem/1010

조합

동적계획법

문제

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

code>>

#include<iostream>

#include <string.h>

int memo[31][31];

long Solve(const int& n, const int& r)

{

if (n == r || r == 0)

return 1;

if (memo[n][r] != -1)

return memo[n][r];

return memo[n][r] = Solve(n - 1, r - 1) + Solve(n - 1, r);

}

int main()

{

std::ios::ios_base::sync_with_stdio(false);

int T, N, M;

std::cin >> T;

while (T-- > 0)

{

std::cin >> N >> M;

memset(memo, -1, sizeof(memo));

printf("%ld\n", Solve(M, N));

}

return 0;

}

저작자표시 비영리

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

1766>문제집 (0)	2019.03.12
1654>랜선 자르기 (0)	2019.02.18
11657>타임머신 (0)	2018.12.04
1786>찾기 (0)	2018.11.26
11062>카드 게임 (0)	2018.11.19

https://www.acmicpc.net/problem/11657

밸만 포드 알고리즘

https://ko.wikipedia.org/wiki/%EB%B2%A8%EB%A8%BC-%ED%8F%AC%EB%93%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.

code>>

#include<iostream>

#include<vector>

#include<tuple>

int main()

{

std::vector<std::tuple<int, int, int>> nodes;

int dis[501];

std::ios::ios_base::sync_with_stdio(false);

int N = 3, M = 4, a,b,c;

std::fill(dis, dis + 501, 987654321);

std::cin >> N >> M;

for (int i = 0; i < M; i++)

{

std::cin >> a >> b >> c;

nodes.emplace_back(std::make_tuple(a, b, c));

}

dis[1] = 0;

bool isCycles = false;

for (size_t i = 0; i < N; i++)

{

for (size_t ii = 0; ii < M; ii++)

{

auto p = nodes[ii];

if (dis[std::get<0>(p)] != 987654321 && dis[std::get<1>(p)] > dis[std::get<0>(p)] + std::get<2>(p))

dis[std::get<1>(p)] = dis[std::get<0>(p)] + std::get<2>(p);

}

for (size_t i = 0; i < M; i++)

{

auto p = nodes[i];

if (dis[std::get<0>(p)] != 987654321 && dis[std::get<1>(p)] > dis[std::get<0>(p)] + std::get<2>(p))

{

isCycles = true;

break;

}

if(isCycles)

printf("-1\n");

else

{

for (int i = 2; i <= N; i++)

printf("%d\n", dis[i] == 987654321 ? -1 : dis[i]);

}

return 0;

}

저작자표시 비영리

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

1654>랜선 자르기 (0)	2019.02.18
1010>다리놓기 (0)	2018.12.17
1786>찾기 (0)	2018.11.26
11062>카드 게임 (0)	2018.11.19
2448>별 찍기 - 11 (0)	2018.11.12

https://www.acmicpc.net/problem/1786

KMP 알고리즘

문제

워드프로세서 등을 사용하는 도중에 찾기 기능을 이용해 본 일이 있을 것이다. 이 기능을 여러분이 실제로 구현해 보도록 하자.

두 개의 문자열 P와 T에 대해, 문자열 P가 문자열 T 중간에 몇 번, 어느 위치에서 나타나는지 알아내는 문제를 '문자열 매칭'이라고 한다. 워드프로세서의 찾기 기능은 이 문자열 매칭 문제를 풀어주는 기능이라고 할 수 있다. 이때의 P는 패턴이라고 부르고 T는 텍스트라고 부른다.

편의상 T의 길이를 n, P의 길이를 m이라고 하자. 일반적으로, n>=m이라고 가정해도 무리가 없다. n<m이면 어차피 P는 T중간에 나타날 수 없기 때문이다. 또, T의 i번째 문자를 T[i]라고 표현하도록 하자. 그러면 물론, P의 i번째 문자는 P[i]라고 표현된다.

1 2 3 4 5 6 7 8 9 …

T : [ A B C D A B C D A B D E ]

| | | | | | X

P : [ A B C D A B D ]

1 2 3 4 5 6 7

문자열 P가 문자열 T 중간에 나타난다는 것, 즉 문자열 P가 문자열 T와 매칭을 이룬다는 것이 어떤 것인지 위와 아래의 두 예를 통해 알아보자. 위의 예에서 P는, T의 1번 문자에서 시작하는 매칭에 실패했다. T의 7번 문자 T[7]과, P의 7번 문자 P[7]이 서로 다르기 때문이다.

그러나 아래의 예에서 P는, T의 5번 문자에서 시작하는 매칭에 성공했다. T의 5～11번 문자와 P의 1～7번 문자가 서로 하나씩 대응되기 때문이다.

1 2 3 4 5 6 7 8 9 …

T : [ A B C D A B C D A B D E ]

| | | | | | |

P : [ A B C D A B D ]

1 2 3 4 5 6 7

가장 단순한 방법으로, 존재하는 모든 매칭을 확인한다면, 시간복잡도가 어떻게 될까? T의 1번 문자에서 시작하는 매칭이 가능한지 알아보기 위해서, T의 1～m번 문자와 P의 1～m번 문자를 비교한다면 최대 m번의 연산이 필요하다. 이 비교들이 끝난 후, T의 2번 문자에서 시작하는 매칭이 가능한지 알아보기 위해서, T의 2～m+1번 문자와 P의 1～m번 문자를 비교한다면 다시 최대 m번의 연산이 수행된다. 매칭은 T의 n-m+1번 문자에서까지 시작할 수 있으므로, 이러한 방식으로 진행한다면 O( (n-m+1) * m ) = O(nm) 의 시간복잡도를 갖는 알고리즘이 된다.

더 좋은 방법은 없을까? 물론 있다. 위에 제시된 예에서, T[7] ≠ P[7] 이므로 T의 1번 문자에서 시작하는 매칭이 실패임을 알게 된 순간으로 돌아가자. 이때 우리는 매칭이 실패라는 사실에서, T[7] ≠ P[7] 라는 정보만을 얻은 것이 아니다. 오히려 i=1…6에 대해 T[i] = P[i] 라고 하는 귀중한 정보를 얻지 않았는가? 이 정보를 십분 활용하면, O(n)의 시간복잡도 내에 문자열 매칭 문제를 풀어내는 알고리즘을 설계할 수 있다.

P 내부에 존재하는 문자열의 반복에 주목하자. P에서 1, 2번 문자 A, B는 5, 6번 문자로 반복되어 나타난다. 또, T의 1번 문자에서 시작하는 매칭이 7번 문자에서야 실패했으므로 T의 5, 6번 문자도 A, B이다.

따라서 T의 1번 문자에서 시작하는 매칭이 실패한 이후, 그 다음으로 가능한 매칭은 T의 5번 문자에서 시작하는 매칭임을 알 수 있다! 더불어, T의 5～6번 문자는 P의 1～2번 문자와 비교하지 않아도, 서로 같다는 것을 이미 알고 있다! 그러므로 이제는 T의 7번 문자와 P의 3번 문자부터 비교해 나가면 된다.

이제 이 방법을 일반화 해 보자. T의 i번 문자에서 시작하는 매칭을 검사하던 중 T[i+j-1] ≠ P[j]임을 발견했다고 하자. 이렇게 P의 j번 문자에서 매칭이 실패한 경우, P[1…k] = P[j-k…j-1]을 만족하는 최대의 k(≠j-1)에 대해 T의 i+j-1번 문자와 P의 k+1번 문자부터 비교를 계속해 나가면 된다.

이 최대의 k를 j에 대한 함수라고 생각하고, 1～m까지의 각 j값에 대해 최대의 k를 미리 계산해 놓으면 편리할 것이다. 이를 전처리 과정이라고 부르며, O(m)에 완료할 수 있다.

이러한 원리를 이용하여, T와 P가 주어졌을 때, 문자열 매칭 문제를 해결하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 T가, 둘째 줄에 문자열 P가 주어진다. 문자열 내에 공백이 포함되어 있을 수도 있음에 유의한다. 물론 공백도 하나의 문자로 인정된다. T와 P의 길이 n, m은 1이상 100만 이하이다.

code>>

#include <iostream>

#include <string>

#include <vector>

int main()

{

std::ios::sync_with_stdio(false);

std::string T, P;

std::getline(std::cin, T);

std::getline(std::cin, P);

std::vector<int> pi(P.size(), 0);

int idx = 0;

for (size_t i = 1; i < P.size(); i++)

{

while (idx > 0 && P[idx] != P[i])

idx = pi[idx - 1];

if (P[idx] == P[i])

pi[i] = ++idx;

}

idx = 0;

std::vector<int> ans;

for (size_t i = 0; i < T.size(); i++)

{

while (idx > 0 && T[i] != P[idx])

idx = pi[idx - 1];

if (T[i] == P[idx])

{

if (idx == P.size() - 1)

{

ans.push_back(i - idx + 1);

idx = pi[idx];

}

else

idx++;

}

printf("%d\n", ans.size());

for (auto i : ans)

printf("%d ", i);

printf("\n");

return 0;

}

저작자표시 비영리

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

1010>다리놓기 (0)	2018.12.17
11657>타임머신 (0)	2018.12.04
11062>카드 게임 (0)	2018.11.19
2448>별 찍기 - 11 (0)	2018.11.12
4367>셀프 넘버 (0)	2018.10.21

https://www.acmicpc.net/problem/11062

동적계획법

문제

근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 카드나 가장 오른쪽에 있는 카드를 가져갈 수 있다. 카드가 더 이상 남아있지 않을 때까지 턴은 반복된다. 게임의 점수는 자신이 가져간 카드에 적힌 수의 합이다.

근우와 명우는 서로 자신의 점수를 가장 높이기 위해 최선의 전략으로 게임에 임한다. 놓여있는 카드의 개수 N과 카드가 놓여있는 상태가 주어졌을 때 근우가 얻는 점수를 구하는 프로그램을 작성하시오.

예를 들어 카드가 [4, 3, 1, 2]로 놓여있다고 하자. 근우는 처음에 4가 적힌 카드를 가져가고, 명우는 3이 적힌 카드를 가져간다. 그리고 근우는 2가 적힌 카드를 가져가고, 명우는 마지막으로 1이 적힌 카드를 가져간다. 이때 근우와 명우는 최선의 전략으로 임했으며, 근우가 얻는 점수는 6이다.

입력

입력의 첫 줄에는 테스트케이스의 수 T가 주어진다.

각 테스트케이스 마다 첫 줄에는 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 두 번째 줄에는 N개의 자연수가 공백으로 구분되어 주어지는데, i번째로 주어지는 수는 왼쪽에서 i번째에 놓인 카드에 적힌 수를 의미한다. 카드에 적혀있는 수는 1이상 10,000이하다.

code >>

#include <iostream>

#include <algorithm>

#include <string.h>

int cards[1001] = { 1,2,5,2 };

int memo[2][1001][1001];

int sel(const int& left, const int& right, const bool& turn)

{

if (left >= right)

if (turn)

return cards[left];

else

return 0;

if (memo[turn][left][right] != -1)

return memo[turn][left][right];

if(turn)

memo[turn][left][right] = std::max(sel(left + 1, right, !turn) + cards[left], sel(left, right - 1, !turn) + cards[right]);

else

memo[turn][left][right] = std::min(sel(left + 1, right, !turn), sel(left, right - 1, !turn));

return memo[turn][left][right];

}

int main()

{

std::ios::ios_base::sync_with_stdio(false);

int t = 1, N = 4;

std::cin >> t;

while (t-- > 0)

{

std::cin >> N;

for (int i = 0; i < N; i++)

std::cin >> cards[i];

memset(memo, -1, sizeof(memo));

printf("%d\n", sel(0, N - 1, 1));

}

return 0;

}

저작자표시 비영리

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

11657>타임머신 (0)	2018.12.04
1786>찾기 (0)	2018.11.26
2448>별 찍기 - 11 (0)	2018.11.12
4367>셀프 넘버 (0)	2018.10.21
1931>회의실배정 (0)	2018.10.20

https://www.acmicpc.net/problem/2448

문제

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.

입력

첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (k ≤ 10)

code >>

#include<iostream>

char stars[3072][6144];

void Star(const int& x , const int& y, const int& N)

{

if (N == 3)

{

stars[y][x] = '*';

stars[y + 1][x - 1] = '*';

stars[y + 1][x + 1] = '*';

stars[y + 2][x - 2] = '*';

stars[y + 2][x - 1] = '*';

stars[y + 2][x] = '*';

stars[y + 2][x + 1] = '*';

stars[y + 2][x + 2] = '*';

return;

}

Star(x, y, N / 2);

Star(x - N / 2, y + N / 2, N / 2);

Star(x + N / 2, y + N / 2, N / 2);

}

int main()

{

std::ios::ios_base::sync_with_stdio(false);

int N = 6;

std::cin >> N;

for (int i = 0; i < N; i++)

{

for (int ii = 0; ii < N * 2 - 1; ii++)

stars[i][ii] = ' ';

}

Star(N - 1, 0, N);

for (int i = 0; i < N; i++)

{

printf("%s", stars[i]);

printf("\n");

}

return 0;

}

저작자표시 비영리

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

1786>찾기 (0)	2018.11.26
11062>카드 게임 (0)	2018.11.19
4367>셀프 넘버 (0)	2018.10.21
1931>회의실배정 (0)	2018.10.20
3665>최종순위 (0)	2018.10.20

https://www.acmicpc.net/problem/4673

문제

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.

양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다.

예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...

n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다.

생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

입력

입력은 없다

code>>

#include<stdio.h>

int Solve(const int & num)

{

if (num < 10)

return num;

return Solve(num / 10) + num % 10;

}

int main()

{

bool selfNum[10001] = {false, };

for (int i = 1; i < 10000; i++)

{

selfNum[i + Solve(i)] = true;

if (!selfNum[i])

printf("%d\n", i);

}

return 0;

}

저작자표시 비영리

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

11062>카드 게임 (0)	2018.11.19
2448>별 찍기 - 11 (0)	2018.11.12
1931>회의실배정 (0)	2018.10.20
3665>최종순위 (0)	2018.10.20
2252>줄 세우기 (0)	2018.10.15

https://www.acmicpc.net/problem/1931

그리디 알고리즘

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

code>>

#include <iostream>

#include <algorithm>

#include <vector>

std::pair<long long, long long> input[100001];

long long time[100001];

bool Compare(const std::pair<long long, long long>& left, const std::pair<long long, long long>& right)

{

if (left.first == right.first)

return left.second < right.second;

else

return left.first < right.first;

}

int main()

{

std::ios::ios_base::sync_with_stdio(false);

int N;

std::cin >> N;

for (int i = 0; i < N; i++)

{

std::pair<long long, long long> p;

std::cin >> p.first >> p.second;

input[i] = p;

}

std::sort(input, input + N, Compare);

auto count = 1;

auto sel = input[0];

for (int i = 1; i < N; i++)

{

if (input[i].first >= sel.second)

{

count++;

sel = input[i];

}

else if(input[i].second <sel.second)

sel = input[i];

}

printf("%d\n", count);

return 0;

}

저작자표시 비영리

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

2448>별 찍기 - 11 (0)	2018.11.12
4367>셀프 넘버 (0)	2018.10.21
3665>최종순위 (0)	2018.10.20
2252>줄 세우기 (0)	2018.10.15
9095>1,2,3 더하기 (0)	2018.10.15

Diademata