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

1405번: 미친 로봇

첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자연수 또는 0이다. 그리고, 동서남북으로 이동할 확률을 모두 더하면 100이다.

www.acmicpc.net

이동할 때마다 그 방향에 부여된 확률을 곱해주면 그 경로로 이동하는 확률을 구할 수 있다.

다양한 경로가 있을 것이고, 각각의 경로로 이동하는 확률을 차곡차곡 더해줌으로써 전체 확률 또한 구할 수 있다.

완전 탐색을 통해 이미 방문한 좌표를 다시 방문하지 않는 경로를 모두 구해서 그 경로로 이동하는 확률을 결과값에 누적해준다면 원하는 결과를 얻을 수 있다.

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
 
bool map[29][29];
vector<double> directPer;
vector<pair<int, int>> dydx = { make_pair(1,0), make_pair(-1,0), make_pair(0,1), make_pair(0,-1) };
int moveMax;
double result = 0;
 
void Solution(int Y, int X, int moveCnt, double multiPercent)
{
    if (moveCnt == moveMax)
    {
        result += multiPercent; // 퍼센트 누적
        return;
    }
 
    for (int i = 0; i < 4; i++) // 동 서 남 북
    {
        int nextY = Y + dydx[i].first, nextX = X + dydx[i].second;
        if (map[nextY][nextX]) continue;
        map[nextY][nextX] = true;
        Solution(nextY, nextX, moveCnt + 1, multiPercent * directPer[i]);
        map[nextY][nextX] = false;
    }
 
}
int main(void)
{
    int E, W, N, S;
    cin >> moveMax >> E >> W >> N >> S;
    directPer.push_back(E*0.01);
    directPer.push_back(W*0.01);
    directPer.push_back(N*0.01);
    directPer.push_back(S*0.01);
 
    map[14][14] = true;    // 중앙에서 시작
 
    Solution(14, 14, 0, 1);
 
    printf("%.9f", result);
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

저작자표시 비영리

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

백준 4641번: Doubles (0)	2020.05.06
백준 2858번: 기숙사 바닥 (0)	2020.05.05
백준 1213번: 팰린드롬 만들기 (0)	2020.04.30
백준 2981번: 검문 (0)	2020.04.30
백준 1062번: 가르침 (0)	2020.04.29

[문제 링크]

1213번: 팰린드롬 만들기

첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다.

www.acmicpc.net

뇌를 자극하는 C++ STL을 공부하면서 배운 내용을 사용해볼 수 있어서 재밌게 푼 문제였다.

처음엔 next_permutation() 함수를 사용해서 구현해보았지만 알파벳 개수가 50개까지 있어서 시간초과가 발생했다.

따라서 다른 방식으로 구현하기로 하였고, 그 방법은 다음과 같다.

1. 입력받은 문자열을 오름차순으로 정렬한다.

2. 문자열의 첫 번째 원소를 가리키는 반복자를 만든 다음 count()함수를 통해 반복자가 가리키는 실제 값이 몇개 존재하는지 확인한다.

IF : 만약 홀수개라면 홀수갯수를 1 증가시킨 다음 (이 때 홀수갯수가 2개 이상이라면 팰린드롬을 만들 수 없기 때문에 " I'm Sorry Hansoo " 출력 후 프로그램을 종료한다.) 값을 char 변수에 저장하고 erase() 멤버함수를 사용해 원소 하나를 삭제한다.

3. 문자 개수의 절반을 stack에 담고 문자열에서 삭제한다. 그리고 반복자가 다음 알파벳을 가리키도록 이동시킨다.

4. 모든 원소에 대해 작업을 마쳤다면 char변수에 저장한 홀수개 알파벳을 문자열 뒤에 붙이고 (없다면 건너뜀)

스택에 저장한 원소를 늦게 들어온 순서대로 문자열 뒤에 붙여준다.

5. 완성!

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
40
41
42
43
44
45
46
47
48

#include <iostream>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
 
int main(void)
{
    string str;
    cin >> str;
    sort(str.begin(), str.end());
    string::iterator iter = str.begin();
 
    stack<char> alpha;
    int cnt = 0, oddCnt = 0, strLen = str.length();
    char oddChar;
    while (cnt < strLen)
    {
        int c = count(str.begin(), str.end(), *iter);
        if (c % 2 != 0)
        {
            oddCnt++; // 홀수개로 존재하는 알파벳 개수카운팅
            if (oddCnt == 2) // 홀수개가 두개 이상이면 안됨
            {
                cout << "I'm Sorry Hansoo" << endl;
                return 0;
            }
            oddChar = *iter;
            iter = str.erase(iter);
        }
        int n = c / 2;
        while (n--)
        {
            alpha.push(*iter);
            iter = str.erase(iter);
        }
        cnt += c;
        iter += c / 2;
    }
    if(oddCnt == 1) str.push_back(oddChar);
    while (!alpha.empty())
    {
        str.push_back(alpha.top());
        alpha.pop();
    }
    cout << str << endl;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

내일도 열심히!

저작자표시 비영리

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

백준 2858번: 기숙사 바닥 (0)	2020.05.05
백준 1405번: 미친 로봇 (0)	2020.05.03
백준 2981번: 검문 (0)	2020.04.30
백준 1062번: 가르침 (0)	2020.04.29
백준 6679번: 싱기한 네자리 숫자 (0)	2020.04.28

[문제 링크]

2981번: 검문

문제 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는

www.acmicpc.net

문제를 보고 뭔가 최대 공약수의 약수들을 출력하면 될 거 같다는 솔루션을 얻는데까지는 오래 걸리지 않았다.

하지만 문제는 M으로 나눴을 때 나머지가 같은 M을 출력하는 것이었기에, 입력받은 숫자 중 가장 작은 숫자를 M으로 하고 그 수를 1씩 감소하면서 나눴을 때 나머지가 같은 M을 벡터에 저장하고, 나머지가 0이 되면 그 때의 M이 최대공약수이므로 최대공약수 M의 약수들을 출력해주는 식으로 구현하려했다.

하지만 999999999, 999999998, 999999997 이런식으로 숫자가 주어지게 되면 1씩 감소해가지고는 시간초과가 날 것이 분명했기 때문에 잘못된 접근이라 생각하고 다른 사람들의 풀이를 참고하였다.

최대공약수를 구하는 유클리드호제법에 대하여 알게 되었고, 3개 이상 숫자들의 최대공약수를 구하는법도 알게되었다.

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
40
41
42
43
44

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> v, result;
int GCD(int a, int b) // 최대공약수 구하기
{
    if (a % b == 0) 
        return b;
 
    return GCD(b, a%b);
}
int main(void)
{
    int testcase;
    cin >> testcase;
    while (testcase--)
    {
        int number;
        cin >> number;
        v.push_back(number);
    }
    sort(v.begin(), v.end());
    int diff = v[1] - v[0];
    for (vector<int>::size_type i = 2; i < v.size(); i++)
        diff = GCD(diff, v[i] - v[i - 1]);
    for (int i = 2; i*i <= diff; i++)
    {
        if (diff%i == 0)
        {
            result.push_back(i);
            result.push_back(diff / i);
        }
    }
    result.push_back(diff);
    sort(result.begin(), result.end());
    vector<int>::iterator iter_end = unique(result.begin(), result.end()); // 중복된 원소를 뒤로 넘김
    for (vector<int>::iterator iter = result.begin(); iter != iter_end; iter++)
        cout << *iter << ' ';
    cout << endl;
    return 0;
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

내일도 열심히!

저작자표시 비영리

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

백준 1405번: 미친 로봇 (0)	2020.05.03
백준 1213번: 팰린드롬 만들기 (0)	2020.04.30
백준 1062번: 가르침 (0)	2020.04.29
백준 6679번: 싱기한 네자리 숫자 (0)	2020.04.28
백준 1074번: 게임 (0)	2020.04.28

[문제 링크]

1062번: 가르침

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

www.acmicpc.net

STL 공부하면서 배운거좀 써먹어보겠다고 까불다가 이틀동안 고생한 문제..

for_each 함수로 입력받은 단어에서 anta, tica 를 제외한 나머지 단어를 검사해서 가르칠 횟수가 남아있고, 아직 배우지 않은 알파벳이라면 alpha 문자열에 추가하는 식으로 구현했는데, 알파벳 하나하나 검사하는 것이 아닌 입력받은 단어 순서대로 검사하게되어 반례가 존재하는 구현이었다...ㅜ ㅜ 다른 사람들의 구현을 보고 모든 알파벳에서 남극언어(a,n,t,i,c)를 다 배운다는 가정하에 배울 수 있는 모든 경우의 수를 구하는 방향으로 다시 구현하였다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<string> voca;
bool alpha[26];
int maxLearn, n, maxCnt = 0;
 
void Solution(int start, int pick)
{
    if (pick == maxLearn) // 다 가르쳤다면
    {
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            bool check = true;
            for (string::size_type j = 0; j < voca[i].size(); j++)
            {
                if (alpha[voca[i][j] - 'a']) continue;
                check = false;
                break;
            }
            if (check) cnt++;
        }
        maxCnt = max(maxCnt, cnt);
        return;
    }
    for (int i = start; i < 26; i++)
    {
        if (alpha[i]) continue;
        alpha[i] = true;
        Solution(i + 1, pick + 1);
        alpha[i] = false;
    }
}
 
int main(void)
{
    cin >> n >> maxLearn;
    for (int i = 0; i < n; i++)
    {
        string str;
        cin >> str;
        voca.push_back(str);
    }
    if (maxLearn < 5)
    {
        cout << 0 << endl;
        return 0;    // antic
    }
    else if (maxLearn == 26)
    {
        cout << n << endl;
        return 0;
    }
    alpha['a' - 'a'] = true;
    alpha['n' - 'a'] = true;
    alpha['t' - 'a'] = true;
    alpha['i' - 'a'] = true;
    alpha['c' - 'a'] = true;
    maxLearn -= 5;
    Solution(1,0);
 
    cout << maxCnt << endl;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

내일도 열심히!

저작자표시 비영리

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

백준 1213번: 팰린드롬 만들기 (0)	2020.04.30
백준 2981번: 검문 (0)	2020.04.30
백준 6679번: 싱기한 네자리 숫자 (0)	2020.04.28
백준 1074번: 게임 (0)	2020.04.28
백준 7453번: 합이 0인 네 정수 (0)	2020.04.26

[문제 링크]

6679번: 싱기한 네자리 숫자

문제 싱기한 네자리 숫자란, [1000,9999]인 10진수 숫자중에서, 다음의 조건을 만족하는 숫자를 말한다. 숫자를 10진수, 12진수, 16진수로 나타낸 다음, 각각의 숫자에 대해, 각 숫자의 자리수를 더했을 때, 세 값이 모두 같아야 한다. 여러분은 싱기한 네자리 숫자를 모두 출력해야 한다. 입력 입력은 주어지지 않는다. 출력 싱기한 네자리 숫자를 오름차순으로 한줄에 하나씩 출력한다. 예제 입력 1 복사 예제 출력 1 복사 2992 2993 29

www.acmicpc.net

매우 쉬운 버전의 완전탐색 문제이다. 1000~9999까지 모든 숫자에 대해서 10진수, 12진수, 16진수 각 자리수를 다 더했을 때 값이 일치하는 숫자를 출력해주면 된다.

#include <iostream>
using namespace std;
 
int main(void)
{
    for (int i = 1000; i < 10000; i++)
    {
        int temp = i;
        int decSum = 0, sum = 0;
        while (temp / 10 != 0)
        {
            decSum += temp % 10;
            temp /= 10;
        }
        decSum += temp;
        temp = i;
        while (temp / 12 != 0)
        {
            sum += temp % 12;
            temp /= 12;
        }
        sum += temp;
        if (decSum != sum) continue;
        temp = i;
        sum = 0;
        while (temp / 16 != 0)
        {
            sum += temp % 16;
            temp /= 16;
        }
        sum += temp;
        if (decSum != sum) continue;
        cout << i << endl;
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

내일도 열심히!

저작자표시 비영리

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

백준 2981번: 검문 (0)	2020.04.30
백준 1062번: 가르침 (0)	2020.04.29
백준 1074번: 게임 (0)	2020.04.28
백준 7453번: 합이 0인 네 정수 (0)	2020.04.26
백준 1038번: 감소하는 수 (0)	2020.04.25

[문제 링크]

1072번: 게임

각 줄에 X와 Y가 주어진다. X는 1,000,000,000보다 작거나 같은 자연수이고, Y는 0보다 크거나 같고, X보다 작거나 같은 자연수이다.

www.acmicpc.net

입력되는 숫자가 1~10억까지이므로 하나하나 검사하면 시간초과가 날 것이 분명하기 때문에 이분탐색을 이용해 풀었다.

충분히 큰 숫자(30억?)부터 시작해 이분탐색으로 더하기 전과 더한 후와 퍼센트가 일치하는 middle 구간을 찾고, 그 구간을 시작으로 1씩 더해가면서 퍼센트가 변하는 middle값을 찾으면 그 값이 정답이 된다.

추가적으로 입력받은 값의 승률이 99퍼센트 이상이면 아무리 더해도 100퍼센트가 나올 수 없기 때문에 불가능(-1)을 리턴 해주었다.

#include <iostream>
using namespace std;
 
const long long MAX = 3000000000;
long long X, Y;
 
long long Solution()
{
    int winRate = (Y * 100) / X;
    if (winRate >= 99) return -1;
    long long start = 0, end = MAX;
    int result = -1;
    while (start <= end)
    {
        long long middle = (start + end) / 2;
        int tempWinRate = ((Y + middle) * 100) / (X + middle);
        if (tempWinRate == winRate)
        {
            result = middle + 1;
            start = middle + 1;
        }
        else
            end = middle - 1;
    }
    return result;
}
int main(void)
{
    cin >> X >> Y;
    cout << Solution() << endl;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

내일도 열심히!

저작자표시 비영리

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

백준 1062번: 가르침 (0)	2020.04.29
백준 6679번: 싱기한 네자리 숫자 (0)	2020.04.28
백준 7453번: 합이 0인 네 정수 (0)	2020.04.26
백준 1038번: 감소하는 수 (0)	2020.04.25
백준 1051번 : 숫자 정사각형 (0)	2020.04.24

[문제 링크]

7453번: 합이 0인 네 정수

문제 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다. A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. 출력 합이 0이 되는 쌍의 개수를 출력한다. 예제 입력 1 복

www.acmicpc.net

이 문제를 접했을 때 마침 STL 컨테이너 set, multiset, map, multimap 에 대해서 공부하고 난 뒤였다.

그래서 빠른 검색속도가 핵심인 multiset을 이용하여 구현해보려고 했었다.

A와 B를 모두 더한 순차열을 저장하고, C와 D를 모두 더한 순차열을 저장하는 두 개의 multiset 객체에

count 멤버함수를 사용하여 C와 D를 더한 객체에 -(A-B) 값(합쳐서 0이 되는 값)이 몇개 존재하는지 확인한 다음 갯수를 카운팅 하는 식으로 코드를 구현했는데 시간초과가 떴다. 연관 컨테이너(set, multiset, map, multimap)는 원소를 검색하는데 로그 시간 복잡도를 보장해준다고 배워서 시간 초과가 안나올줄 알았는데 시간초과가 나와서 당황했다.

구글링하다 접하게된 정보인데 아무래도 위에서 설명하는 특성때문에 시간초과가 난거같다. ㅜㅜ

그래서 vector컨테이너를 사용해서 구현하였다.

분명 multiset과 같이 이진 검색을 이용한 알고리즘인데 시간초과가 안난게 아직 풀리지 않은 의문이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<int> CD;
long long zeroSum = 0;
 
void Solution(int here)
{
    int lower_iter, upper_iter;
    lower_iter = lower_bound(CD.begin(), CD.end(), -here) - CD.begin();
    upper_iter = upper_bound(CD.begin(), CD.end(), -here) - CD.begin();
 
    if (lower_iter == upper_iter) return;
 
    zeroSum += upper_iter - lower_iter;
}
 
int main(void)
{
    int col;
    int a[4001], b[4001], c[4001], d[4001];
    cin >> col;
 
    for(int i=0; i<col; i++)
        cin >> a[i] >> b[i] >> c[i] >> d[i];
 
    for(int i=0; i<col; i++)
        for (int j = 0; j < col; j++)
            CD.push_back(c[i] + d[j]);
 
    sort(CD.begin(), CD.end());
 
    for (int i = 0; i < col; i++)
        for (int j = 0; j < col; j++)
            Solution(a[i] + b[j]);
 
    cout << zeroSum << endl;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

내일도 열심히!

저작자표시 비영리

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

백준 6679번: 싱기한 네자리 숫자 (0)	2020.04.28
백준 1074번: 게임 (0)	2020.04.28
백준 1038번: 감소하는 수 (0)	2020.04.25
백준 1051번 : 숫자 정사각형 (0)	2020.04.24
백준 3085번: 사탕 게임 (c++) (0)	2020.04.24

[문제 링크]

1038번: 감소하는 수

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

www.acmicpc.net

큐를 이용한 솔루션을 생각하기 전에 한참 고민한 문제였다.

큐의 첫번째 원소의 일의 자리 수 보다 작은 숫자들을 뒤에 붙여서 다시 큐에 추가하는식으로 구현하였다.

#include <iostream>
#include <queue>
using namespace std;
 
queue<long long> q;
long long Solution(int N)
{
    if (N == 0) return 0;
    int lastNum, cnt = 0;
    for (int i = 1; i < 10; i++)
        q.push(i);
    while (!q.empty())
    {
        int lastNum = q.front() % 10;
        for (int i = 0; i < lastNum; i++)
            q.push((q.front() * 10) + i);
        cnt++;
        if (cnt == N) return q.front();
        q.pop();
    }
    return -1;
}
int main(void)
{
    int N;
    cin >> N;
    cout << Solution(N) << endl;
    return 0;
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

내일도 열심히!

저작자표시 비영리

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

백준 1074번: 게임 (0)	2020.04.28
백준 7453번: 합이 0인 네 정수 (0)	2020.04.26
백준 1051번 : 숫자 정사각형 (0)	2020.04.24
백준 3085번: 사탕 게임 (c++) (0)	2020.04.24
백준 2503번: 숫자 야구 (c++) (0)	2020.04.23

언제나 처음처럼