문제 풀이

 

 다양한 방법으로 풀이가 가능한 문제로 저는 포인터를 역 방향으로 참조하여 문제를 풀었습니다.

 

 

코드

 

1
2
3
4
5
6
7
8
9
10
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
    string d;
    cin >> d;
    sort(d.rbegin(), d.rend());
    cout << d;
}

 

 

제출 결과

 

 

 

문제 출처

 

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

 

1427번: 소트인사이드

첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

1978번: 소수 찾기 (백준 온라인 저지, C++)  (0) 2019.04.02
2108번: 통계학 (백준 온라인 저지, C++)  (0) 2019.04.02
2750번: 수 정렬하기 (백준 온라인 저지, C++)  (0) 2019.04.01
6064번: 카잉 달력 (백준 온라인 저지, C++)  (0) 2019.03.31
1475번: 방 번호 (백준 온라인 저지, C++)  (0) 2019.03.31

문제 해설

 

 단순한 정렬 문제입니다. 버블 소트를 활용하여 풀이하였습니다.

 

 

코드

 

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>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int n;
    int d[1000];
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> d[i];
 
    //bubble sort
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n - i - 1; j++)
        {
            if (d[j] > d[j + 1])
            {
                int tmp = d[j];
                d[j] = d[j + 1];
                d[j + 1] = tmp;
            }
        }
    }
 
    for (int i = 0; i < n; i++)
        cout << d[i] << '\n';
 
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

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

 

2750번: 수 정렬하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

2108번: 통계학 (백준 온라인 저지, C++)  (0) 2019.04.02
1427번: 소트인사이드 (백준 온라인 저지, C++)  (0) 2019.04.01
6064번: 카잉 달력 (백준 온라인 저지, C++)  (0) 2019.03.31
1475번: 방 번호 (백준 온라인 저지, C++)  (0) 2019.03.31
2775번: 부녀회장이 될테야 (백준 온라인 저지, C++)  (0) 2019.03.31

풀이 과정

 

 arr에 map을 입력 받고, 시작점인 (0, 0)부터 탐색을 시작합니다. 해당 칸까지 이동하였을 때, 걸린 최소 비용을 dist 배열에 저장해 줍니다. dist 배열은 매우 큰 수로 초기값을 정해 줍니다. 

 

 간단한 예를 들어, dist에 파란색 경로의 최소 비용이 저장되어 있을 때, 주황색 경로의 최소 비용이 더 작은 경우 dist에 저장된 값을 주황색 경로의 값으로 갱신하여 줍니다. 따라서 탐색이 종료되면, dist[n-1][n-1]에는 (n-1, n-1)까지 가는 최소 비용이 저장되어 있게 됩니다.

 

 

코드

 

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#include <queue>
using namespace std;
 
int n;
int arr[100][100], dist[100][100];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
 
void search()
{
    queue <pair<int, int>> q;
    q.push(make_pair(0, 0));
 
    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (nx < n && ny < n && nx >= 0 && ny >= 0)
            {
                int ndist = arr[nx][ny] + dist[x][y];
                if (ndist < dist[nx][ny])
                {
                    q.push(make_pair(nx, ny));
                    dist[nx][ny] = ndist;
                }
            }
        }
    }
    return;
}
 
int main(){
 
    int t;
    scanf("%d", &t);
 
    for (int tc = 1; tc <= t; tc++)
    {
        scanf("%d", &n);
 
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                scanf("%1d", &arr[i][j]);
                dist[i][j] = 99999999;
            }
 
        dist[0][0] = 0;
        search();
 
        printf("#%d %d\n", tc, dist[n-1][n-1]);
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&&&

 

SW Expert Academy

SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

swexpertacademy.com

 

'algorithm codes > samsung sw expert academy' 카테고리의 다른 글

6731. 홍익이의 오델로 게임 (삼성 SW Academy, C++)  (0) 2019.04.01
1226. [S/W 문제해결 기본] 7일차 - 미로1 (삼성 SW Academy, C++)  (0) 2019.04.01

문제 풀이

 

 이 문제는 단순히 구현을 했을 때는 시간 초과가 나게 됩니다. 따라서 x를 고정시켜 주고, 이 x에 따라 나올 수 있는 y를 찾아가면서 문제를 풀어야 합니다.

 

 예를 들어, 10 12 3 9의 경우 3이 x의 자리에 올 때 y의 자리에 올 수 있는 값은 3, 1, 11, 9, ... 이며 이 때 각각 10년의 텀을 두고 발생하게 됩니다. 따라서 답은 3년에 3*10을 더한 33년이 됩니다. 주의할 점은 % 연산의 경우 0부터 시작하기 때문에 이를 고려하여 코드를 구성해야 합니다.

 

 만약 가장 처음에 y 자리에 왔던 값이 다시 나타나게 된다면, 이는 한 주기를 모두 지났다는 뜻이 되므로 종말 년도를 넘어섰다는 뜻이 됩니다. 따라서 -1을 출력합니다.

 

 또는 최소 공배수와 최대 공약수를 활용하여 종말 년도를 먼저 계산하고, 이를 넘어서는 경우를 찾아주는 것도 가능합니다.

 

 

코드

 

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
#include <iostream>
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int t;
    cin >> t;
 
    while (t--)
    {
        int m, n, x, y;
        cin >> m >> n >> x >> y;
 
        int ans = x, b = (x - 1) % n + 1;
        int tmp = b;
 
        while (1)
        {
            if (b == y)
                break;
            
            b = (b + m - 1) % n + 1; 
            ans += m;
 
            if (tmp == b)
            {
                ans = -1;
                break;
            }
        }
 
        cout << ans << "\n";
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

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

 

6064번: 카잉 달력

문제 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

1427번: 소트인사이드 (백준 온라인 저지, C++)  (0) 2019.04.01
2750번: 수 정렬하기 (백준 온라인 저지, C++)  (0) 2019.04.01
1475번: 방 번호 (백준 온라인 저지, C++)  (0) 2019.03.31
2775번: 부녀회장이 될테야 (백준 온라인 저지, C++)  (0) 2019.03.31
5622번: 다이얼 (백준 온라인 저지, C++)  (0) 2019.03.31

풀이

방 번호 문제의 경우, 6과 9가 겹치는 부분만 처리해주면 크게 어렵지 않은 문제입니다.

문자를 하나 하나 비교하여 배열을 증가시키는 경우 코드가 길어지기 때문에 '0'의 아스키 코드 값이 48인 것을 활용하여 문제를 풀었습니다. 또는 int형으로 숫자를 입력받고 10으로 0이 될 때까지 나누어 나머지 값을 인덱스로 참조하여 배열을 증가시켜 주는 방법도 가능합니다.

 

코드

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 <cstdio>
 
using namespace std;
 
int main() {
 
    int a[9] = { 0, };
    char line[8];
    scanf("%s", &line);
 
    int i = 0;
    while (line[i])
    {
        int x = line[i] - 48;
        if (x == 9)
            a[6]++;
        else
            a[x]++;
        i++;
    }
    
    a[6] = (a[6] + 1) / 2;
 
    int m = 0;
    for (int i = 0; i < 10; i++)
    {
        if (a[i] > m)
            m = a[i];
    }
 
    printf("%d\n", m);
    
    return 0;
}

 

제출 결과

 

문제 출처

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

 

1475번: 방 번호

첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

2750번: 수 정렬하기 (백준 온라인 저지, C++)  (0) 2019.04.01
6064번: 카잉 달력 (백준 온라인 저지, C++)  (0) 2019.03.31
2775번: 부녀회장이 될테야 (백준 온라인 저지, C++)  (0) 2019.03.31
5622번: 다이얼 (백준 온라인 저지, C++)  (0) 2019.03.31
2908번: 상수 (백준 온라인 저지, C++)  (0) 2019.03.31

문제

 “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다”

모든 거주자가 해당 계약 조건을 지키고 입주하였을 때, k층에 n호에는 몇 명이 살고 있는가? 단, 아파트는 0층부터 있고 각 층에는 1호부터 있으며 0층의 i호에는 i명이 산다.

 

입력

 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두번째 줄에 정수 n이 주어진다. (k와 n은 1에서 14까지의 정수)

 

출력

 각각의 Test case에 대해서 해당 집에 거주민 수를 출력.

 

코드

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
#include <iostream>
 
using namespace std;
 
int main() {
 
ios_base:: sync_with_stdio(false);
cin.tie(NULL);
 
    int t;
    cin >> t;
 
    while (t--)
    {
        int n, k;
        cin >> n >> k;
        
        int d[15][15] = { 0, };
        
        for (int i = 0; i <= n; i++)
        {
            for (int j = 1; j <= k; j++)
            {
                if (i == 0)
                    d[i][j] = j;
                else
                    d[i][j] = d[i][j - 1] + d[i - 1][j];
            }
        }
 
        cout << d[n][k] << '\n';
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter
 
 

 

제출 결과

 

문제 출처

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

 

2775번: 부녀회장이 될테야

첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다. (1 <= k <= 14, 1 <= n <= 14)

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

6064번: 카잉 달력 (백준 온라인 저지, C++)  (0) 2019.03.31
1475번: 방 번호 (백준 온라인 저지, C++)  (0) 2019.03.31
5622번: 다이얼 (백준 온라인 저지, C++)  (0) 2019.03.31
2908번: 상수 (백준 온라인 저지, C++)  (0) 2019.03.31
2675번: 문자열 반복 (백준 온라인 저지, C++)  (0) 2019.03.31

입력

알파벳 대문자로 이루어진 단어

 

출력

다이얼을 걸기 위해 필요한 시간

 

문제 풀이

단순히 각각의 케이스를 if문으로 나열하는 것도 가능합니다. 그러나 코드가 길어지는게 싫었어요ㅠㅠ

그래서 A의 아스키 코드 값이 65인 것을 활용하여 문제를 풀었습니다.

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
int main() {
 
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    char a[16];
    cin >> a;
    int ans = 0;
    for (int i = 0; a[i]; i++)
    {
        int x = a[i];
        if (x >= 90)
            x = (x - 67) / 3 + 3;
        else if (x >= 83)
            x = (x - 66) / 3 + 3;
        else
            x = (x - 65) / 3 + 3;
        ans += x;
    }
    cout << ans << '\n';
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

제출 결과

 

문제 출처

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

 

5622번: 다이얼

문제 상근이의 할머니는 아래 그림과 같이 오래된 다이얼 전화기를 사용한다. 전화를 걸고 싶은 번호가 있다면, 숫자를 하나를 누른 다음에 금속 핀이 있는 곳 까지 시계방향으로 돌려야 한다. 숫자를 하나 누르면 다이얼이 처음 위치로 돌아가고, 다음 숫자를 누르려면 다이얼을 처음 위치에서 다시 돌려야 한다. 숫자 1을 걸려면 총 2초가 필요하다. 1보다 큰 수를 거는데 걸리는 시간은 이보다 더 걸리며, 한 칸 옆에 있는 숫자를 걸기 위해선 1초씩 더 걸린다.

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

1475번: 방 번호 (백준 온라인 저지, C++)  (0) 2019.03.31
2775번: 부녀회장이 될테야 (백준 온라인 저지, C++)  (0) 2019.03.31
2908번: 상수 (백준 온라인 저지, C++)  (0) 2019.03.31
2675번: 문자열 반복 (백준 온라인 저지, C++)  (0) 2019.03.31
11654: 아스키 코드 (백준 온라인 저지, C++)  (0) 2019.03.30

입력

상근이가 칠판에 적은 세자리의 두 수

 

출력

두 수의 숫자를 거꾸로 읽었을 때, 더 큰 수

 

코드

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
#include <cstdio>
#include <cmath>
using namespace std;
int main() {
 
    int a = 0;
    int b = 0;
    for (int i = 0; i < 3; i++)
    {
        int x;
        scanf("%1d", &x);
        a += pow(10, i) * x;
    }
    for (int i = 0; i < 3; i++)
    {
        int x;
        scanf("%1d", &x);
        b += pow(10, i) * x;
    }
    if (a > b)
        printf("%d\n", a);
    else
        printf("%d\n", b);
    
    return 0;
}

 

제출 결과

 

문제 출처

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

 

2908번: 상수

문제 상근이의 동생 상수는 수학을 정말 못한다. 상수는 숫자를 읽는데 문제가 있다. 이렇게 수학을 못하는 상수를 위해서 상근이는 수의 크기를 비교하는 문제를 내주었다. 상근이는 세 자리 수 두 개를 칠판에 써주었다. 그 다음에 크기가 큰 수를 말해보라고 했다. 상수는 수를 다른 사람과 다르게 거꾸로 읽는다. 예를 들어, 734과 893을 칠판에 적었다면, 상수는 이 수를 437과 398로 읽는다. 따라서, 상수는 두 수중 큰 수인 437을 큰 수라고 말할

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

2775번: 부녀회장이 될테야 (백준 온라인 저지, C++)  (0) 2019.03.31
5622번: 다이얼 (백준 온라인 저지, C++)  (0) 2019.03.31
2675번: 문자열 반복 (백준 온라인 저지, C++)  (0) 2019.03.31
11654: 아스키 코드 (백준 온라인 저지, C++)  (0) 2019.03.30
10039: 평균 점수 (백준 온라인 저지, C++)  (0) 2019.03.30

+ Recent posts

티스토리툴바