문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

입력받은 수 부터 하나씩 줄여가며 모든 경우의 수를 다 구해서 생성자를 찾는 방식으로 풀었음

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using System;
 
class Program
{
    static void Main(string[] args)
    {
        int iN = int.Parse(Console.ReadLine());
        int iResult = 0;
        for(int i = iN; i > 0; i--)
        {
            string temp = i.ToString();
            int total = i;
            for(int j = 0; j < temp.Length; j++)
            {
                total = total + int.Parse(temp[j].ToString());
            }
            if(total == iN) iResult = i;
        }
        Console.WriteLine(iResult);
    }
}
 cs

 

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

 

2231번: 분해합

문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+

www.acmicpc.net

 

'void Algorithm' 카테고리의 다른 글

백준 문제 번호 : 1018 - 체스판 다시 칠하기  (0) 2020.09.08
백준 문제 번호 : 7568 - 덩치  (0) 2020.08.27
백준 문제 번호 : 2798 - 블랙잭  (0) 2020.08.20
백준 문제 번호 : 11729 - 하노이 탑 이동 순서  (0) 2020.08.18
백준 문제 번호 : 10870 - 피보나치 수 5  (0) 2020.08.13

문제

카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.

한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.

김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.

이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.

N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.

입력

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는다.

합이 M을 넘지 않는 카드 3장을 찾을 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.

 

모든 경우의 수를 다 구해서 더하는 방식으로 풀었다.

첫 번째 예제의 경우라면

 

5 + 6 + 7 = 18

5 + 6 + 8 = 19

5 + 6 + 9 = 20

5 + 7 + 8 = 20

5 + 7 + 9 = 21

5 + 8 + 9 = 22

6 + 7 + 8 = 21

6 + 7 + 9 = 22

6 + 8 + 9 = 23

7 + 8 + 9 = 24

...

M은 21 이므로 값은 21이다.

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
using System;
using System.Linq;
 
class Program
{
    static void Main(string[] args)
    {
        int[] iInput = Console.ReadLine().Split().Select(n=>int.Parse(n)).ToArray();
        int N = iInput[0];
        int M = iInput[1];
        int[] iNnum = Console.ReadLine().Split().Select(n=>int.Parse(n)).ToArray();
        int iMax = 0;
        for(int i = 0; i < N-2; i++)
        {
            for(int j = i+1; j < N-1; j++)
            {
                for(int k = j+1; k < N; k++)
                {
                    int temp = iNnum[i] + iNnum[j] + iNnum[k];
                    if(temp > iMax && temp <= M) iMax = temp;
                }
            }
        }
        Console.WriteLine(iMax);
    }
}
 cs

풀이를 적다보니 M과 같은 값이 나온다면 더 이상 반복문을 수행하지 않고 결과 값을 출력해도 될 것 같아서 

조금 수정해보았다.

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
using System;
using System.Linq;
 
class Program
{
    static void Main(string[] args)
    {
        int[] iInput = Console.ReadLine().Split().Select(n=>int.Parse(n)).ToArray();
        int N = iInput[0];
        int M = iInput[1];
        int[] iNnum = Console.ReadLine().Split().Select(n=>int.Parse(n)).ToArray();
        int iMax = 0;
        for(int i = 0; i < N-2; i++)
        {
            for(int j = i+1; j < N-1; j++)
            {
                for(int k = j+1; k < N; k++)
                {
                    int temp = iNnum[i] + iNnum[j] + iNnum[k];
                    if(temp > iMax && temp <= M) 
                    {
                        iMax = temp;
                        if(iMax == M) break;
                    }
                }
                if(iMax == M) break;
            }
            if(iMax == M) break;
        }
        Console.WriteLine(iMax);
    }
}
 cs

위의 결과가 수정한 코드 아래가 수정 전 코드이다. 시간이 아주 살짝 줄어든 걸 볼 수 있다.

 

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

 

2798번: 블랙잭

문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 ��

www.acmicpc.net

 

'void Algorithm' 카테고리의 다른 글

백준 문제 번호 : 7568 - 덩치  (0) 2020.08.27
백준 문제 번호 : 2231 - 분해합  (0) 2020.08.22
백준 문제 번호 : 11729 - 하노이 탑 이동 순서  (0) 2020.08.18
백준 문제 번호 : 10870 - 피보나치 수 5  (0) 2020.08.13
백준 문제 번호 : 10872 - 팩토리얼  (0) 2020.08.12

문제

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.

  1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
  2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.

이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.

아래 그림은 원판이 5개인 경우의 예시이다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

 

출력

첫째 줄에 옮긴 횟수 K를 출력한다.

두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

 

재귀함수를 이용한 하노이 탑 이동 구현

 

문제는 복잡해 보이지만 의외로 간단하다.

 

제일 밑에 있는 n 번째 판을 목적지인 3으로 이동 시키기 위해선

n-1번째 부터 그 위에 있는 판들을 경유지인 2로 이동시켜야 한다.

그래서 제일 먼저 호출되는 재귀함수가 (n-1, 1, 3, 2) 로 호출되는 것이다. 

2로 이동시킨 판들은 다시 n-1번째 부터 그위에 있는 판들을 1로 이동시켜서 n 번쨰 위치한 판을 3으로 이동시켜야 한다.

그래서 (n-1,2,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
using System;
using System.Text;
 
class Program
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        StringBuilder sValue = new StringBuilder();
        int count = 0;
        Hanoi(n,1,2,3,ref count, ref sValue);
        sValue.Insert(0,count+"\n");
        Console.WriteLine(sValue);
    }
    
    static void Hanoi(int n, int from, int via, int to, ref int count, ref StringBuilder sValue)
    {
        if(n==0) return;
        count++;
        Hanoi(n-1, from, to, via, ref count, ref sValue);
        sValue.Append(from +" " + to+"\n");
        Hanoi(n-1, via, from, to, ref count, ref sValue);
    }
}
 cs

 

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

 

11729번: 하노이 탑 이동 순서

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로

www.acmicpc.net

 

'void Algorithm' 카테고리의 다른 글

백준 문제 번호 : 2231 - 분해합  (0) 2020.08.22
백준 문제 번호 : 2798 - 블랙잭  (0) 2020.08.20
백준 문제 번호 : 10870 - 피보나치 수 5  (0) 2020.08.13
백준 문제 번호 : 10872 - 팩토리얼  (0) 2020.08.12
백준 문제 번호 : 1002 - 터렛  (0) 2020.08.11

+ Recent posts

티스토리툴바