문제출처: https://www.acmicpc.net/problem/14647


풀이

빙고판에서 9의 총 갯수에서 9가 가장많이 나오는 행과 열  중 9가 더 많이등장한 행or열의 값을 뺀 값이 정답입니다.

값은 행/열 배열값을 의미하고, 각각의 행or열에서 등장하는 9의 갯수가 담겨져있습니다.

이것을 그대로 소스코드로 구현하면 됩니다.


코드

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
#include<iostream>
using namespace std;
int max_val;
int arr[500][500];
int row[500], col[500];
int sum;
int func(int num);
int main()
{
    cin.tie(0);
    cin.sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> arr[i][j];
            row[i] += func(arr[i][j]);
            col[j] += func(arr[i][j]);
            sum += func(arr[i][j]);
        }
    }
    //행에대해서 탐색 
    for (int i = 0; i < n; i++)
    {
        if (row[i] > max_val)max_val = row[i];
    }
    //열에대해서 탐색
    for (int j = 0; j < m; j++)
    {
        if (col[j] > max_val)max_val = col[j];
    }
    //전체 9의 갯수 값에서 행,열중 큰 값을 뺀값이 정답
    cout << sum - max_val <<endl;
}
int func(int num)
{
    int cnt = 0;
    while (num)
    {
        if (num % 10== 9)cnt++;
        num /= 10;
    }
    return cnt;
}
cs


결과


저작자표시

'문제풀이(BOJ) > 시뮬레이션(구현)' 카테고리의 다른 글

[백준 13300] 방 배정  (0) 2020.03.11
[백준 17224] APC는 왜 서브태스크 대회가 되었을까?  (3) 2020.03.10
[백준 15953] 상금 헌터  (0) 2020.03.10
[백준 1018] 체스판 다시 칠하기  (0) 2020.02.07
[백준 5533] 유니크  (0) 2020.01.19

문제출처: https://www.acmicpc.net/problem/16395


풀이

파스칼의 삼각형같은 이항계수의 성질을 이용하는 문제는 dp로 접근하는게 제일 쉬운 것 같습니다.

각 행의 맨 왼쪽 값을 1로 고정시켜놓고 n+1Cr+1=nCr+nCr+1 의 성질을 이용하여 dp식을 세웠습니다.

*각 행의 맨 오른쪽 값1은 최초의 값 1설정 후 dp계산시 저절로 1로 고정된 상태가 됩니다.


코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n, k;
int dp[31][31];
int main()
{
    cin >> n >> k;
    for (int i = 0; i < 31; i++)
    {
        dp[i][0] = 1;
    }
    for (int i = 1; i < 31; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        }
    }
    cout << dp[n-1][k-1] << endl;
    
}
cs


결과


저작자표시

'문제풀이(BOJ) > 다이나믹 프로그래밍' 카테고리의 다른 글

[백준 11055] 가장 큰 증가 부분수열  (0) 2020.03.09
[백준 1309] 동물원  (0) 2020.01.09
[백준 1010] 다리 놓기  (0) 2019.12.11
[백준 11052] 카드 구매하기  (0) 2019.12.11
[백준 1912] 연속합  (0) 2019.12.08

문제출처: https://www.acmicpc.net/problem/17224


풀이

문제가 길다보니 괜히 어렵게 접근하여 낚인 문제입니다.

pair벡터와 2번째 원소를기준으로 정렬하는 sort함수로 풀었는데 자꾸 100점이 뜨길래 계속 고민했지만 복잡하게 생각할 필요가 없는 문제였습니다.

벡터와 알고리즘 헤더를 이용하지않고도 1차원 배열하나만 있으면 간단하게 풀리는 문제입니다. 너무 어렵게 생각했나봅니다..

저처럼 pair벡터와 2번째 원소를 기준으로 정렬시켜서 계산한 분들이 계시다면 분명 문제에서 알려준대로 예시2,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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int arr[101];
int main()
{
    int n, l, k, sub1, sub2, sum = 0;
    cin >> n >> l >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> sub1 >> sub2;
        if (sub2 <= l)
            arr[i] = 140;
        else if (sub1 <= l)
            arr[i] = 100;
    }
    sort(arr, arr + n, greater<int>());
    for (int i = 0; i < k; i++)
    {
        sum += arr[i];
    }
    cout << sum << endl;
    
}
cs


결과








저작자표시

'문제풀이(BOJ) > 시뮬레이션(구현)' 카테고리의 다른 글

[백준 13300] 방 배정  (0) 2020.03.11
[백준 14647] 준오는 조류혐오야!!  (0) 2020.03.10
[백준 15953] 상금 헌터  (0) 2020.03.10
[백준 1018] 체스판 다시 칠하기  (0) 2020.02.07
[백준 5533] 유니크  (0) 2020.01.19

문제출처: https://www.acmicpc.net/problem/15953


풀이

그냥 조건대로 코딩하면 됩니다.

정답률이 36프로라니....


코드

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
#include<iostream>
using namespace std;
int main()
{
    int t, a, b, sum; cin >> t;
    for (int i = 0; i < t; i++)
    {
        sum = 0;
        cin >> a >> b;
        if (a == 1)
            sum += 5000000;
        else if (a == 2 || a == 3)
            sum += 3000000;
        else if (a >= 4 && a <= 6)
            sum += 2000000;
        else if (a >= 7 && a <= 10)
            sum += 500000;
        else if (a >= 11 && a <= 15)
            sum += 300000;
        else if (a >= 16 && a <= 21)
            sum += 100000;
 
        if (b == 1)
            sum += 5120000;
        else if (b == 2 || b == 3)
            sum += 2560000;
        else if (b >= 4 && b <= 7)
            sum += 1280000;
        else if (b >= 8 && b <= 15)
            sum += 640000;
        else if (b >= 16 && b <= 31)
            sum += 320000;
        cout << sum << '\n';
    }
}
cs


결과



저작자표시

'문제풀이(BOJ) > 시뮬레이션(구현)' 카테고리의 다른 글

[백준 14647] 준오는 조류혐오야!!  (0) 2020.03.10
[백준 17224] APC는 왜 서브태스크 대회가 되었을까?  (3) 2020.03.10
[백준 1018] 체스판 다시 칠하기  (0) 2020.02.07
[백준 5533] 유니크  (0) 2020.01.19
[백준 9517] 아이 러브 크로아티아  (0) 2020.01.19

문제출처: https://www.acmicpc.net/problem/14954


풀이

영어로된 문제라 당연스럽게 구글번역으로 한글로 바꿔서 풀었습니다ㅋㅋ;

문제를 요약하면, N의 자릿값을 계속 더해나갈 때 그 값이 언젠간 1이 되면 Happy number가 되고, 아닐 시 Unhappy number가 됩니다.

아닐 경우 문제에서 예로 들어준 5를 보면

5-> 25-> 29-> 85-> 89-> 145-> 42-> 20->4->16->37->58->89->----- 순으로 이어지는데 결국 기존에 나왔던 89가 또한번 나타나므로 

결국,  수식을 계속 계산해나갈 때 기존의 값이 또 나오면 Unhappy number임을 알 수 있습니다.

핵심은 한번 계산할 때 마다 담아놨던 값들에 대해서 일일히 또 나타나는 값인지 확인해야한다는 것입니다.

그 과정에서 주석 친 29~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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>v;
int main()
{
    int n, temp = 0;
    cin >> n;
    if (n == 1)
    {
        cout << "HAPPY" << endl;
        return 0;
    }
    temp = n;
    int num = 0;
    while (1)
    {
        while (temp)
        {
            num += (temp % 10) * (temp % 10);
            temp /= 10;
        }
        if (num == 1)
        {
            cout << "HAPPY" << endl;
            return 0;
        }
        /*v.push_back(num);
        temp = num;
        */
        //누적되어있는 값들중에서 기존에있었던 값인지확인
        for (int i = 0; i < v.size(); i++)
        {
            if (v[i] == num)
            {
                cout << "UNHAPPY" << endl;
                return 0;
            }
        }
        //재시작
        v.push_back(num);
        temp = num;
        num = 0;
    }
    
    
}
cs


결과



저작자표시

'문제풀이(BOJ) > 규칙찾기' 카테고리의 다른 글

[백준 1676] 팩토리얼 0의 개수  (0) 2020.08.27
[백준 1652] 누울 자리를 찾아라  (2) 2020.01.15
[백준 1855] 암호  (0) 2020.01.06
[백준 3076] 상근이의 체스판  (0) 2020.01.03
[백준 1551] 수열의 변화  (0) 2020.01.03

문제출처: https://www.acmicpc.net/problem/11055


풀이

약 3주만에 알고리즘 문제를 다시 풀어보려는데 감이 많이 떨어져서 쉬운 문제를 찾다가 풀어본 문제입니다.

대충 문제를 읽고 dp문제같아서 dp로 풀었는데 맞았습니다. 

arr[i]>arr[j]일 때 ( 앞의값보다 뒤의값이 클 때) dp[i]값을 갱신하는 식만 작성할줄 알면 될 것 같습니다.


코드

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
#include<iostream>
#include<algorithm>
int arr[1001], dp[1001];
using namespace std;
int main()
{
    int n, sum = 0;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        //arr[i]값을 dp에 복사한다.
        dp[i] = arr[i];
        //하나씩 비교해보며 가장 큰 증가부분수열구함
        for (int j = 0; j <= i; j++)
        {
            // [1, 100, 2] 일 때
            //증가수열이므로 무조건 뒷값이 앞값보다커야함
            if (arr[i] > arr[j])
            {
                //정답인dp[i]값을 갱신시켜나감
                if (dp[i] < dp[j] + arr[i])dp[i] = dp[j] + arr[i];
            }
        }
        //정답을 갱신시킴
        sum = max(sum, dp[i]);
    }
    cout << sum << endl;
}
cs


결과




저작자표시

'문제풀이(BOJ) > 다이나믹 프로그래밍' 카테고리의 다른 글

[백준 16395] 파스칼의 삼각형  (0) 2020.03.10
[백준 1309] 동물원  (0) 2020.01.09
[백준 1010] 다리 놓기  (0) 2019.12.11
[백준 11052] 카드 구매하기  (0) 2019.12.11
[백준 1912] 연속합  (0) 2019.12.08

문제 출처: https://www.acmicpc.net/problem/1956


풀이

사소한 오타 하나때문에 15번정도 제출오류가 났던 문제입니다.

풀이 방법순으로 적어보면,

1. map을 INF로 초기화해놓는다.

2. 플로이드와샬을 돌려서 map에 각 노드에서 각 노드로 가는 최단거리를 저장한다.

3. 각 노드에서 노드로 가는 길 중 INF가 아닐때만(길이 있을 때만) 사이클의 최단길이를 비교합니다.

4. map[i][j]!=INF&&map[j][i]!=INF이면 사이클이 존재하는 것이고, 결국 temp가 INF라면 사이클이없으므로, -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
#include<iostream>
#include<algorithm>
using namespace std;
int INF = 4000000;
int map[400][400];
int main()
{
    int v, e, a, b, c;
    cin >> v >> e;
    for (int i = 0; i < 400; i++)
    {
        for (int j = 0; j < 400; j++)
        {
            map[i][j] = INF;
        }
    }
    for (int i = 0; i < e; i++)
    {
        cin >> a >>b>> c;
        map[a- 1][b - 1] = c;
    }
    for (int k = 0; k < v; k++)
    {
        for (int i = 0; i < v; i++)
        {
            for (int j = 0; j < v; j++)
            {
                if (map[i][j] > map[i][k] + map[k][j])
                    map[i][j] = map[i][k] + map[k][j];
            }
        }
    }
    int temp = INF;
    for (int i = 0; i < v; i++)
    {
        for (int j = 0; j < v; j++)
        {
            if (i == j)
                continue;
            if (map[i][j] != INF && map[j][i] != INF)
            {
                temp = min(temp, map[i][j] + map[j][i]);
            }
        }
    }
    if (temp == INF)cout << -1 << endl;
    else cout << temp;
}
cs



결과



저작자표시

'문제풀이(BOJ) > 플로이드와샬' 카테고리의 다른 글

[백준 1389] 케빈 베이컨의 6단계 법칙  (0) 2020.02.05
[백준 2458] 키 순서  (1) 2020.01.24
[백준 10159] 저울  (0) 2020.01.24
[백준 11403] 경로 찾기  (0) 2020.01.15

문제 출처: https://www.acmicpc.net/problem/12761


풀이

문제에서 주어진 조건들로 하여금 BFS를 돌리면 됩니다. 해결해야할 조건은 다음과 같습니다.


1. 현위치에서 한칸 왼쪽가기

2. 현위치에서 한칸 오른쪽가기

3. 현위치에서 a칸 왼쪽 가기

4. 현위치에서 a칸 오른쪽가기

5. 현위치에서 b칸 왼쪽 가기

6. 현위치에서 b칸 오른쪽가기

7. 현위치의 a배 왼쪽가기

->현위치의 a배는 무조건 값이 0보다 작게되므로 불가능 

8. 현위치의 a배 오른쪽가기

9. 현위치의 b배 왼쪽가기 

->현위치의 b배는 무조건 값이 0보다 작게되므로 불가능 

10.현위치의 b배 오른쪽가기


총 8가지 조건만 잘 작성하면됩니다.


코드

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include<queue>
using namespace std;
int a, b, n, m;
int map[100001], visited[100001], cnt;
void bfs(int start,int  cnt);
int main(void)
{
    cin >> a >> b >> n >> m;
    bfs(n,0);
}
void bfs(int start,int cnt)
{
    queue<pair<int, int>>q;
    q.push({ start,0 });
    visited[start] = 1;
    while (!q.empty())
    {
        start = q.front().first;
        cnt = q.front().second;
        q.pop();
        if (start == m)
        {
            cout << cnt << endl;
            return;
        }
       //한칸 왼쪽 가기
        if(start-1>=0&&!visited[start-1])
        {
            visited[start - 1] = 1;
            q.push({ start - 1,cnt + 1 });
        }
        //한칸 오른쪾 가기
        if (start + 1 <= 100000 && !visited[start + 1])
        {
            visited[start + 1] = 1;
            q.push({ start + 1,cnt + 1 });
        }
 
        //현위치에서 a만큼 왼쪽가기
        if (start - a >= 0 && !visited[start - a])
        {
            visited[start - a] = 1;
            q.push({ start - a,cnt + 1 });
        }
        //현위치에서 a만큼 오른쪽가기
        if (start + a <= 100000 && !visited[start + a])
        {
            visited[start + a] = 1;
            q.push({ start + a,cnt + 1 });
        }
        //현위치에서 b만큼 왼쪽 가기
        if (start - b >= 0 && !visited[start - b])
        {
            visited[start - b] = 1;
            q.push({ start - b,cnt + 1 });
        }
        //현위치에서 b만큼 오른쪽 가기
        if (start + b >= 0 && !visited[start + b])
        {
            visited[start + b] = 1;
            q.push({ start + b,cnt + 1 });
        }
        //현 위치의 a배 오른쪽가기
        if (start *a <= 100000 && !visited[start * a])
        {
            visited[start * a] = 1;
            q.push({ start * a,cnt + 1 });
        }
        
        //현 위치의 b배 오른쪽가기
        if (start * b <= 100000 && !visited[start * b])
        {
            visited[start * b] = 1;
            q.push({ start * b,cnt + 1 });
        }
    }
}
cs


결과



저작자표시

'문제풀이(BOJ) > DFS,BFS' 카테고리의 다른 글

[백준 2206] 벽 부수고 이동하기  (0) 2020.02.11
[백준 17836] 공주님을 구해라!  (0) 2020.02.10
[백준 1759] 암호 만들기  (0) 2020.02.06
[백준] 촌수계산  (0) 2020.01.20
[백준 2589] 보물섬(BFS)  (0) 2020.01.17

+ Recent posts

티스토리툴바