알파벳 찾기

문제번호 : 10809번

문제링크 : https://www.acmicpc.net/problem/10809

문제

알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다.

출력

각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다.

만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단어의 첫 번째 글자는 0번째 위치이고, 두 번째 글자는 1번째 위치이다.

예제

입력

baekjoon

출력

1 0 -1 -1 2 -1 -1 -1 -1 4 3 -1 -1 7 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

풀이

코드

#include<iostream>
#include<cstring>
#include<string>
#define IOFAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
​
int main(){
    IOFAST();
    int alp[27];
    memset(alp, -1, sizeof(alp));
    string str;
    cin >> str;
​
    for (int i = 0; i < str.length(); i++){
        int temp = (int)(str[i] - 'a');
        if (alp[temp] == -1){
​
            alp[temp] = i;
        }
    }
    for (int i = 0; i < 26; i++){
        cout << alp[i] << ' ';
    }
    return 0;
}

​

소수 구하기

문제번호 : 1929번

문제링크 : https://www.acmicpc.net/problem/1929

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1≤M≤N≤1,000,000)

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제

입력

3 16

출력

3
5
7
11
13

풀이

소수는 자신보다 작은 ( 1을 제외한 )수로 나누어 떨어지지 않는 수를 소수라고 한다.

n= a*b이라고 할때, a >= √n 이면, a * b = n = √n * √n 이므로, b<=√n 된다.

이를 통해서 자신보다 작은 모든 수가 아니라 자신의 제곱근값보다 작은 수들을 소수 판별하는 것이 더 효율적이다.

<에라토스테네스의 체 >

모든 자연수는 하나 이상의 소수의 곱으로 표현할 수 있다.

이것을 이용해서 소수를 구하는 방법이다.

2가 아닌 2의 배수들은 소수가 아니다.

3이 아닌 3의 배수들은 소수가 아니다.

5가 아닌 5의 배수들을 소수가 아니다.

....

이를 이용해서 소수를 구해보자.

코드

#include<iostream>
#include<cstring>
#define IOFAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int main(){
    IOFAST();
    
    int m, n;
    bool arr[1000001];
    cin >> m >> n; 
    memset(arr, true, sizeof(arr));
    arr[0] = arr[1] = false; // 0과 1은 소수가 아님.
    
    for (int i = 2; i<=sqrt(1000000); i++){ //2~ 1000까지 소수 판별(중복방지를 위해서)
​
        if (arr[i]== false) continue;   //소수가 아니면 PASS
​
        for (int j = 2; j <= n/i; j++){ //소수(자신)를 제거한 소수의 배수들을 모두 제거(i*j<=n)
            arr[i*j] = false;
        }
    }
    for (int i = m; i <= n; i++){
        if (arr[i]==true) cout << i << '\n';
    }
    return 0;
}

​

숫자의 개수

문제번호 : 2577 번

문제링크 : https://www.acmicpc.net/problem/2577

문제

세 개의 자연수 A, B, C가 주어질 때 A×B×C를 계산한 결과에 0부터 9까지 각각의 숫자가 몇 번씩 쓰였는지를 구하는 프로그램을 작성하시오.

예를 들어 A = 150, B = 266, C = 427 이라면

A × B × C = 150 × 266 × 427 = 17037300 이 되고,

계산한 결과 17037300 에는 0이 3번, 1이 1번, 3이 2번, 7이 2번 쓰였다.

입력

첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 같거나 크고, 1,000보다 작은 자연수이다.

출력

첫째 줄에는 A×B×C의 결과에 0 이 몇 번 쓰였는지 출력한다. 마찬가지로 둘째 줄부터 열 번째 줄까지 A×B×C의 결과에 1부터 9까지의 숫자가 각각 몇 번 쓰였는지 차례로 한 줄에 하나씩 출력한다.

예제

입력

150
266
427

출력

3
1
0
2
0
0
0
2
0
0

풀이

코드 보안

1)

int temp = int(result[i]) - 48; //문자를 10진수로 바꾸면 +48 됨으로 빼줘야함.

===> 다른 형변환 방법이 있을까?

로 하면 출력초과가 나온다. 해결할 방법 찾기

코드

#include<iostream>
#include<string>
#include<cstdlib>
#define IOFAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
int arr[10];
int main(){
    IOFAST();
    int a, b, c,avg;
​
    cin >> a >> b >> c;
    avg = a*b*c;
    string result = to_string(avg);
    for (int i = 0; i < (signed)result.size(); i++){
        int temp = int(result[i]) - 48; //문자를 10진수로 바꾸면 +48 됨으로 빼줘야함.(또는 '0')
        arr[temp]++;
    }
    for (int i = 0; i <= 9; i++){
        cout << arr[i] << '\n';
    }
​
​
    return 0;
​
}

​ ​

이친수

문제번호 : 2193 번

문제링크 : https://www.acmicpc.net/problem/2193

문제

0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.

1. 이친수는 0으로 시작하지 않는다.

2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.

예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.

N(1≤N≤90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 N자리 이친수의 개수를 출력한다.

예제

입력

3

출력

2

풀이

n =1 -> 1

n=2 -> 10 (1에 0붙음)

n=3 -> 100,101 (10에 0과 1이 붙음)

n=4 -> 1000,1001, 1010 (100에 0과 1이 붙고, 101에 0이 붙음)

n=5 -> 10000,10001, 10010, 10100,10101

즉, n-1의 이친수 들 중에서 0으로 끝나는 수에는 0과 1를 붙이고, 1로 끝나는 수에는 0을 붙일 수 있다.

a(n)(0) = a(n-1)(0) + a(n-1)(1)

a(n)(1) =a(n-1)(0)=a(n-2)(0)+a(n-2)(1)

결과적으로 a(n) 은 a(n-1)+a(n-2) 이 됨을 알수 있다.

코드

#include<iostream>
#define IOFAST() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
//long long int a[91][2];
long long int a[91];    
int main(){
    IOFAST();
    int n, i;
    cin >> n;
    //a[1][0] = 0; a[1][1] = 1;
    a[1] = 1;
    for (i = 2; i <= n; i++){
        //a[i][0] = a[i - 1][0] + a[i - 1][1];
        //a[i][1] = a[i - 1][0];
        a[i]=a[i-1]+a[i-2];
    }
​
    //cout << a[n][0]+a[n][1];
    cout << a[n];
    return 0;
​
}

​ ​

포도주 시식

문제번호 : 2156 번

문제링크 : https://www.acmicpc.net/problem/2156

문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.

2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오.

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

예제

입력

6
6
10
13
9
8
1

출력

33

풀이

이문제는 계단오르기 문제와 흡사하다. 연속해서 3개의 잔을 선택할 수 없다. 하지만 계단오르기 문제와는 다르게 마지막 잔을 꼭 먹어야 할 필요가 없다. 그렇다면 경우는 세가지이다. >

1. n을 마시고, n-1잔을 마시고 n-2잔을 마시지 않은 경우

2. n을 마시고, n-1잔을 마시지않고 n-1잔을 마신 경우

3. n을 마시지 않고, n-1,n-2잔을 마신 경우

를 코드로 나타내면

for ( ; ; ){
        dp[i] = max(data[i] + data[i - 1] + dp[i - 3] , data[i] + dp[i - 2]);
        dp[i] = dp[i-1] > dp[i] ? dp[i-1] : dp[i]; //d[i]를 선택하지 않는 경우
        }

코드

#include<iostream>
#include<cstring>
#include<algorithm>
#define max(a,b) a>b?a:b
int main(){
    int n, i;
    scanf("%d", &n);
    int* data = new int[n + 1];
    int* dp = new int[n + 1];
    memset(data, 0, sizeof(data));
    memset(dp, 0, sizeof(dp));  
​
    for (i = 1; i <= n; i++)    scanf("%d", data + i);
    dp[1] = data[1];
    dp[2] = data[1] + data[2];
    for (i = 3; i <= n; i++){
        dp[i] = max(data[i] + data[i - 1] + dp[i - 3] , data[i] + dp[i - 2]);
        dp[i] = dp[i-1] > dp[i] ? dp[i-1] : dp[i];
    }
    printf("%d", dp[n]);
}