문제

N진수 게임
튜브가 활동하는 코딩 동아리에서는 전통적으로 해오는 게임이 있다. 이 게임은 여러 사람이 둥글게 앉아서 숫자를 하나씩 차례대로 말하는 게임인데, 규칙은 다음과 같다.

숫자를 0부터 시작해서 차례대로 말한다. 첫 번째 사람은 0, 두 번째 사람은 1, … 열 번째 사람은 9를 말한다.
10 이상의 숫자부터는 한 자리씩 끊어서 말한다. 즉 열한 번째 사람은 10의 첫 자리인 1, 열두 번째 사람은 둘째 자리인 0을 말한다.
이렇게 게임을 진행할 경우,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, …
순으로 숫자를 말하면 된다.

한편 코딩 동아리 일원들은 컴퓨터를 다루는 사람답게 이진수로 이 게임을 진행하기도 하는데, 이 경우에는
0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, …
순으로 숫자를 말하면 된다.

이진수로 진행하는 게임에 익숙해져 질려가던 사람들은 좀 더 난이도를 높이기 위해 이진법에서 십육진법까지 모든 진법으로 게임을 진행해보기로 했다. 숫자 게임이 익숙하지 않은 튜브는 게임에 져서 벌칙을 받는 굴욕을 피하기 위해, 자신이 말해야 하는 숫자를 스마트폰에 미리 출력해주는 프로그램을 만들려고 한다. 튜브의 프로그램을 구현하라.

풀이

• 입력받은 10진수를 n진수로 변환한다.

코드

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

class Solution {

    public String getNDigitNum(int n,int digit)
    {
        StringBuilder sb = new StringBuilder();
        int curNumber = n;
        if(curNumber == 0)
        {
            return "0";
        }
        while(curNumber > 0)
        {
            if(curNumber % digit < 10)
            {
                sb.append(curNumber % digit);
            }
            else
            {
                sb.append((char)(curNumber % digit - 10 + 'A'));
            }
            curNumber /= digit;
        }
        return sb.reverse().toString();
    }
    //0, 1, 1, 0, 1, 1, 1, 0, 0
    //digit,number,people,count
    public String solution(int n, int t, int m, int p) {
        String nDigitString;
        StringBuilder answerStrBuild = new StringBuilder();
        int curT = 1;
        int num=0;
        int countT = 0;
        while(true)
        {
            nDigitString = getNDigitNum(num++,n);
            for(int idx=0;idx<nDigitString.length();idx++)
            {
                if(curT == p)
                {
                    answerStrBuild.append(nDigitString.charAt(idx));
                    countT++;
                    if(countT == t)
                    {
                        return answerStrBuild.toString();
                    }
                }
                curT++;
                if(curT > m)
                {
                    curT = 1;
                }
            }
        }
    }
}

10진수 -> n진수 변환

m진수 -> n진수 변환이 아닌 10진수 - > n진수 변환인 점 유의

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public String getNDigitNum(int n,int digit)
{
	StringBuilder sb = new StringBuilder();
	int curNumber = n;
	if(curNumber == 0)
	{
		return "0";
	}
	while(curNumber > 0)
	{
		if(curNumber % digit < 10)
		{
			sb.append(curNumber % digit);
		}
		else
		{
			sb.append((char)(curNumber % digit - 10 + 'A'));
		}
		curNumber /= digit;
	}
	return sb.reverse().toString();
}    

n진수 변환 -> 10진수 변환

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public static int nToTenDigit(String num, int N){

	char[] numArray = num.toCharArray();
	int ans = 0;
	for(int i=0;i < numArray.length;i++)
	{
		if(numArray[i] >= 'A')
		{
			//10진수 이상의 진수
			ans = ans * N + (numArray[i] - 'A' + 10);
		}
		else
		{
			//10진수 미만의 n
			ans = ans * N + (numArray[i] - '0');
		}
		
	}
}

메모

내가 직접 생각해서 구현한 방식은 비효율적이어서 인터넷에서 코드를 참조했다.

개요

백준 문제 1476번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 20분
https://www.acmicpc.net/problem/1476

문제

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.

지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)

우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.

예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.

E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S 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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <iostream>

using namespace std; 

void solve()
{
    int answerE = 0,answerS = 0,answerM = 0;
    int eMax = 15;
    int sMax = 28;
    int mMax = 19;
    int year = 0;
    int curE = 0;
    int curS = 0;
    int curM = 0;
    cin >> answerE >> answerS >> answerM;
    while(1)
    {
        curE++;
        curS++;
        curM++;
        year++;
        if(curE > eMax)
        {
            curE = 1;
        }
        if(curS > sMax)
        {
            curS = 1;
        }
        if(curM > mMax)
        {
            curM = 1;
        }
        if(answerE == curE && answerS == curS && answerM == curM)
        {
            cout << year;
            break;
        }
    }
    


}

int main()
{
    solve();
}

풀이

1. 뭔가 규칙성을 찾아서 풀기 보다는 그냥 문제의 조건에 맞춰 E,S,M 값과 년도를 늘려나가는데,
   입력된 값과 현재 E,S,M이 일치하면 년도를 출력하면 되는 완전탐색 문제임.

배울 점, 메모

완전탐색인 것을 알고 풀었기 때문에 쉬운 문제라고 생각함.
유형을 아직 익히는 것이기 때문에 유형과 문제를 1:1로 매칭시키는 것이 필요함.

개요

백준 문제 2873번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : ?분
https://www.acmicpc.net/problem/2873

문제

상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다.

어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다.

이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가장 오른쪽 아래 칸에서 도착할 것이다. 롤러코스터는 현재 있는 칸과 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 이동할 수 있다. 각 칸은 한 번 방문할 수 있고, 방문하지 않은 칸이 있어도 된다.

각 칸에는 그 칸을 지나갈 때, 탑승자가 얻을 수 있는 기쁨을 나타낸 숫자가 적혀있다. 롤러코스터를 탄 사람이 얻을 수 있는 기쁨은 지나간 칸의 기쁨의 합이다. 가장 큰 기쁨을 주는 롤러코스터는 어떻게 움직여야 하는지를 구하는 프로그램을 작성하시오.

코드

1
2
3
4
5
6
7

상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다.

어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다.

이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가장 오른쪽 아래 칸에서 도착할 것이다. 롤러코스터는 현재 있는 칸과 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 이동할 수 있다. 각 칸은 한 번 방문할 수 있고, 방문하지 않은 칸이 있어도 된다.

각 칸에는 그 칸을 지나갈 때, 탑승자가 얻을 수 있는 기쁨을 나타낸 숫자가 적혀있다. 롤러코스터를 탄 사람이 얻을 수 있는 기쁨은 지나간 칸의 기쁨의 합이다. 가장 큰 기쁨을 주는 롤러코스터는 어떻게 움직여야 하는지를 구하는 프로그램을 작성하시오.

풀이

일단 당연히 모든 점을 순회할 수 있으면 가장 높은 점수가 나온다.
그래서 모든 점을 순회가능한 경우에는 모두 순회하는데
문제는 가로와 세로가 짝수인 경우에는 모두 순회할 수 없고 딱 한점을 피해서 가면 순회할 수 있어
그 딱 한점을 피해서 가야한다.
한 점을 피하는 건 우선 전체 점을 둘러보면서 가장 작은 점을 찾는다.
그 뒤가 어려운데, 그 점의 좌표를 기준으로 최대한 많은 점을 순회하며 바로 왼쪽에 도달한 다음,
왼쪽 아래 대각선으로 이동 오른쪽으로 이동 이후 마지막까지 순회하면 완성

배울 점, 메모

나는 이 문제를 자력으로 풀진 못했다.
모든 점을 순회하면 되는 두 경우는 생각했으나
가로 세로가 짝수인 경우에는 안된다는 것을 찾지 못했고 검색을 통해
알았지만, 실제로 구현할려고 생각하면 좀 복잡해서 이해하기도 힘들었다.
이 문제를 풀면서 부족했던 능력은

1. 문제를 읽고 케이스별을 놓침(문제에 대한 시간을 많이 쓰지 않음) - 여러 케이스를 직접 만들어서 하나씩 해야함
2. 구현력 부족 - 많은 시간을 들여서 노력하는 수 밖에 없음

개요

백준 문제 11399번을 풀면서 어려웠던 점과 코드를 정리한다.
소요 시간 : 10분
https://www.acmicpc.net/problem/11399

문제

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

코드

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 <algorithm>

using namespace std;

vector<int> v;

void solve()
{
	int N;	
	cin >> N;
	for(int i=0;i<N;i++)
	{
		int time;
		cin >> time;
		v.push_back(time);
	}
	sort(v.begin(),v.end());
	//소요시간
	int sumTime = 0;
	//소요시간 + 현재 소요 시간
	int resultTime = 0;
	for(int i=0;i<N;i++)
	{
		sumTime += v[i];
		resultTime += sumTime;
	}
	cout << resultTime;



}

int main()
{
	solve();
	

}

풀이

그리디..?까지 생각하지 않아도 걸리는 시간이 적은 순으로 정렬한 뒤
소요시간은 더하면 되는 문제
운영체제의 스케줄링에서 입력이 동시에 왔을 때 SJT 정책과 동일하게 생각하면 된다.

배울 점, 메모

이렇게 쉬운 문제인데도 식이나 코드가 바로 나오지 않았는데
수학적인 면이나 생각을 빠르게 이끌어내는 연습이 부족한 것 같다.