반응형

문제출처

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


문제풀이

이중 for문을 사용하면 되는 간단한 문제


소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <cstring>
int main() {
    int tc, repeat, len;
    char s[21];
    scanf("%d", &tc);
    while(tc--) {
        scanf("%d %s", &repeat, &s);
        len=strlen(s);
        for(int i=0; i<len; i++) {
            for(int j=0; j<repeat; j++) {
                printf("%c", s[i]);
            }
        }
        printf("\n");
    }
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 1655] 가운데를 말해요  (0) 2019.04.16
[BOJ 1157] 단어공부  (0) 2019.04.15
[BOJ 13458] 시험감독  (0) 2019.04.15
[BOJ 1057] 토너먼트  (0) 2019.04.15
[BOJ 1094] 막대기  (0) 2019.04.15
반응형

문제출처

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

 

문제풀이

단순 시뮬레이션 문제입니다. 단지 결과값이 int범위를 벗어날 수 있다는 점을 감안하면 됩니다.

이때 저는 배열을 main안의 지역변수에서 선언했더니 실행이 안되는 상황이 발생했습니다. 

그 이유는 다음과 같습니다.

지역 변수를 선언하면 메모리의 스택 영역이라는 작은 영역에 할당이 됩니다. 그래서 지역 변수로 너무 큰 배열을 선언하면 메모리가 부족해서 에러가 뜹니다.

메모리 구조에 대해 다시 한번 공부하게된 문제

 

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int a[1000001];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, b, c;
    long long ans=0;
    cin>>n;
    for(int i=0; i<n; i++) cin>>a[i];
    cin>>b>>c;
    for(int i=0; i<n; i++) {
        ans++;
        a[i] -= b;
        if(a[i]<=0) continue;
        ans += (a[i] % c == 0 ? a[i] / c : a[i] / c + 1);
    }
    cout<<ans<<endl;
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 1157] 단어공부  (0) 2019.04.15
[BOJ 2675] 문자열 반복  (0) 2019.04.15
[BOJ 1057] 토너먼트  (0) 2019.04.15
[BOJ 1094] 막대기  (0) 2019.04.15
[BOJ 11718] 그대로 출력하기  (0) 2019.04.15
반응형

문제출처

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


문제풀이

/**
* 다음라운드의 자신의 번호 = (현재 자신의 번호 + 1) / 2
* ==> int형 기준
* 다음라운드의 번호가 같다면 break해준다.
* Ex) 7, 8 번 매칭이라면 (7+1)/2 = 8, (8+1)/2 = 8 이므로 1라운드에 매칭하는 것
*/


소스코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, kim, lim;
    cin>>n>>kim>>lim;
    int round=1;
    while(n) {
        if((kim+1)/2 == (lim+1)/2) break;
        kim = (kim+1)/2;
        lim = (lim+1)/2;
        round++;
        n/=2;
    }
    if(!n) round=-1;
    cout<<round<<"\n";
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 2675] 문자열 반복  (0) 2019.04.15
[BOJ 13458] 시험감독  (0) 2019.04.15
[BOJ 1094] 막대기  (0) 2019.04.15
[BOJ 11718] 그대로 출력하기  (0) 2019.04.15
[SWEA 1244] 최대 상금  (4) 2019.02.27
반응형

문제출처

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

 

문제풀이

/**
 * 초기 막대기의 길이는 64이며 길이가 x인 막대를 만드는 문제이다.
 * stick 변수는 초기값을 가지고 있으면서 현재 자른 막대기의 길이를 가지는 변수입니다.
 * x를 만드는 방식은 다음과 같다.
 * 1. 현재 막대기가 x보다 크다면 막대기를 반으로 자른다.
 * 2. 현재 막대기가 x보다 작거나 같다면 막대기를 붙인다.
 * => 막대기를 붙였으므로 남은 x의 길이를 알기 위해 x를 막대기 길이만큼 빼줍니다.
 */

소스코드

#include <iostream>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int x, stick=64;
    cin>>x;
    int cnt=0;
    while(x>0) {
        if(stick > x) stick/=2;
        else {
            cnt++;
            x -= stick;
        }
    }
    cout<<cnt<<endl;
    return 0;
}
반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 13458] 시험감독  (0) 2019.04.15
[BOJ 1057] 토너먼트  (0) 2019.04.15
[BOJ 11718] 그대로 출력하기  (0) 2019.04.15
[SWEA 1244] 최대 상금  (4) 2019.02.27
[BOJ 3908] 서로 다른 소수의 합  (0) 2019.02.27
반응형

문제출처

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

 

문제풀이

그대로 입력받고 출력해주는 문제이다. cin을 사용하지 말고 getline을 사용하면 된다.

 

소스코드

C++

#include <iostream>
#include <string>
using namespace std;
int main() {
    string str;
    for(int i=0; i<100; i++) {
        getline(cin, str);
        cout<<str<<endl;
    }
    return 0;
}

 

C

#include <stdio.h>
#include <stdlib.h>

int main()
{
    char name[101];
    name[0]='\0';
    while(fgets(name,100,stdin)){
        printf("%s",name);
        name[0]='\0';
    }
    return 0;
}

 

반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 1057] 토너먼트  (0) 2019.04.15
[BOJ 1094] 막대기  (0) 2019.04.15
[SWEA 1244] 최대 상금  (4) 2019.02.27
[BOJ 3908] 서로 다른 소수의 합  (0) 2019.02.27
[BOJ 2407] 조합  (0) 2019.02.26
반응형

문제출처

https://www.swexpertacademy.com/


문제풀이

전체탐색을 통해 풀이하였습니다. base case조건으로 교환 횟수와 현재까지 바꾼 갯수가 같으면 

지금까지의 결과와 현재 결과중 큰 값을 result에 저장했습니다.


소스코드


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
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
int n, result;
string num;
void dfs(int cur, int cnt) {
    if(cnt==n) {
        result=max(result, stoi(num));
        return;
    }
    for(int i=cur; i<num.size(); i++) {
        for(int j=i+1; j<num.size(); j++) {
            if(num[i] <= num[j]) {
                swap(num[i], num[j]);
                dfs(i, cnt + 1);
                swap(num[i], num[j]);
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int tc;
    cin>>tc;
    for(int i=1; i<=tc; i++) {
        cin>>num>>n;
        result=0;
        dfs(0,0);
        cout<<"#"<<i<<" "<<result<<"\n";
    }
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 1094] 막대기  (0) 2019.04.15
[BOJ 11718] 그대로 출력하기  (0) 2019.04.15
[BOJ 3908] 서로 다른 소수의 합  (0) 2019.02.27
[BOJ 2407] 조합  (0) 2019.02.26
[BOJ 10974] 모든 순열  (0) 2019.02.25
반응형

문제출처

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


문제풀이

소스코드 참고


소스코드

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 <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAX 1120
using namespace std;
bool isPrime[MAX+1];
vector<int> prime;
int dp[MAX+1][15];
// 에라스토테네스의 체를 사용하여 MAX까지의 소수를 모두 구한다.
void eratosthenes() {
    memset(isPrime, 1, sizeof(isPrime));
    isPrime[0]=isPrime[1]=0;
    int sqrtn=int(sqrt(MAX));
    for(int i=2; i<=sqrtn; i++) {
        if(isPrime[i]) {
            for(int j=i*i; j<=MAX; j+=i) {
                isPrime[j]=0;
            }
        }
    }
    for(int i=2; i<=MAX; i++) {
        if(isPrime[i])
            prime.push_back(i);
    }
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    eratosthenes();
    dp[0][0]=1;
    // dp[n][k] = n을 k개의 소수의 합으로 만들수 있는 갯수
    // 즉 n을 k개로 만드는 것의 합은 dp[n-prime[i]][k-1]의 합과 같다.
    for(int i=0; i<prime.size(); i++) {
        for(int j=MAX; j>=prime[i]; j--) {
            for(int k=1; k<15; k++) {
                dp[j][k]+=dp[j-prime[i]][k-1];
            }
        }
    }
    int tc,n,k;
    cin>>tc;
    while(tc--) {
        cin>>n>>k;
        cout<<dp[n][k]<<endl;
    }
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 11718] 그대로 출력하기  (0) 2019.04.15
[SWEA 1244] 최대 상금  (4) 2019.02.27
[BOJ 2407] 조합  (0) 2019.02.26
[BOJ 10974] 모든 순열  (0) 2019.02.25
[BOJ 9996] 한국이 그리울 땐 서버에 접속하지  (0) 2019.02.22
반응형

문제출처

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



소스코드

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 <string>
#include <algorithm>
using namespace std;
string dp[101][101];
/**
 * 조합공식을 이용해 풀이했지만 자꾸 틀렸습니다가 나와 멘붕온 문제
 * 이유는 unsingend long long의 범위도 넘기 때문이였다.
 * 결국 구글링을 통해 solve...
 */
string addNum(string a, string b) {
    unsigned long long int sum = 0;
    string ret;
    while(!a.empty() || !b.empty() || sum) {
        if(!a.empty()) {
            sum+=a.back() - '0';
            a.pop_back();
        }
        if(!b.empty()) {
            sum+=b.back() - '0';
            b.pop_back();
        }
        ret.push_back((sum%10) + '0');
        sum/=10;
    }
    reverse(ret.begin(), ret.end());
    return ret;
}
string combination(int n, int r) {
    if(n==r || r==0)
        return "1";
    string &ret = dp[n][r];
    if(ret != "")
        return ret;
    ret=addNum(combination(n-1, r-1), combination(n-1, r));
    return ret;
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,m;
    cin>>n>>m;
    cout<<combination(n,m);
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[SWEA 1244] 최대 상금  (4) 2019.02.27
[BOJ 3908] 서로 다른 소수의 합  (0) 2019.02.27
[BOJ 10974] 모든 순열  (0) 2019.02.25
[BOJ 9996] 한국이 그리울 땐 서버에 접속하지  (0) 2019.02.22
[BOJ 9935] 문자열 폭발  (0) 2019.02.21
반응형

문제출처

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


문제풀이

1
2
3
4
5
6
/**
 * 재귀적으로 풀이하였음. visit을 이용해서 같은 숫자가 반복출력되지 않도록 해야한다.
 * printPermutation에서 number는 순열에 추가될 숫자 digit은 순열의 현재 자릿수, n은 입력받은 n을 뜻한다.
 * 아래 main for문에서는 첫번째 숫자를 선택해주고 printPermutation의 for문을 통해 n자리수 순열을 만들어
 * 출력해주면 되는 문제이다.
 */
cs


소스코드


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
#include <iostream>
#include <vector>
using namespace std;
vector<bool> visit;
vector<int> permutation;
void printPermutation(int number, int digit, int n) {
    permutation[digit]=number;
    if(digit==n) {
        for(int i=1; i<=n; i++) cout<<permutation[i]<<" ";
        cout<<"\n";
        return;
    }
    for(int i=1; i<=n; i++) {
        if(visit[i]) continue;
        visit[i]=1;
        printPermutation(i, digit+1, n);
        visit[i]=0;
    }
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin>>n;
    visit.resize(n+1); permutation.resize(n+1);
    for(int i=1; i<=n; i++) {
        visit[i]=1;
        printPermutation(i, 1, n);
        visit[i]=0;
    }
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 3908] 서로 다른 소수의 합  (0) 2019.02.27
[BOJ 2407] 조합  (0) 2019.02.26
[BOJ 9996] 한국이 그리울 땐 서버에 접속하지  (0) 2019.02.22
[BOJ 9935] 문자열 폭발  (0) 2019.02.21
[BOJ 1764] 듣보잡  (0) 2019.02.20
반응형

문제출처

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


문제풀이

1
2
3
4
5
6
7
/**
 * 패턴의 형식이 접두사 *  접미사 형태인데 이것을 이용하면 된다.
 * find함수로 '*'의 위치를 찾아내서 접두사 접미사를 구한다. 처음에는 오직 접두사 접미사만 같으면
 * 되는줄 알았으나 생각해보니 예외 케이스가 있었다. 패턴이 swj*jsw 이고 파일이름이 swjsw인 경우이다.
 * 이를 해결하기 위해 먼저 파일의 길이와 패턴길이를 판별한뒤 접두사와 접미사가 같은지 판별하였다.
 * 생각보다 흥미로웠던 문제
 */
cs


소스코드


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 <string>
using namespace std;
const string yes="DA\n", no="NE\n";
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, suffixSize;
    string pattern, fileName, prefix, suffix;
    cin>>n>>pattern;
 
    int asterikIdx = pattern.find('*');
    prefix=pattern.substr(0,asterikIdx);
    suffix=pattern.substr(asterikIdx+1);
    suffixSize=suffix.size();
 
    while(n--) {
        cin>>fileName;
        if(fileName.size() < pattern.size()-1) {
            cout<<no;
            continue;
        }
        else if(fileName.size() == pattern.size()-1) {
            if(fileName == pattern.substr(0, asterikIdx) + pattern.substr(asterikIdx+1))
                cout<<yes;
            else cout<<no;
            continue;
        }
        else {
            string prefixFileName = fileName.substr(0, asterikIdx);
            string suffixFileName = fileName.substr(fileName.size()-suffixSize);
            if(prefix==prefixFileName && suffix==suffixFileName)
                cout<<yes;
            else
                cout<<no;
            continue;
        }
    }
    return 0;
}
cs


반응형
저작자표시

'Algorithm' 카테고리의 다른 글

[BOJ 2407] 조합  (0) 2019.02.26
[BOJ 10974] 모든 순열  (0) 2019.02.25
[BOJ 9935] 문자열 폭발  (0) 2019.02.21
[BOJ 1764] 듣보잡  (0) 2019.02.20
[BOJ 1213] 펠린드롬 만들기  (0) 2019.02.19

+ Recent posts

티스토리툴바