개발 블로그

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.

• 1+1+1+1
• 2+1+1 (1+1+2, 1+2+1)
• 2+2
• 1+3 (3+1)

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 10,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

3
4
7
10

4
8
14

문제

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

출력

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

접근 방법

단순하게 생각을 했다.  GCF + ACDEB를 더하려면 어떻게 해야할까?

아직 각 알파벳에 어떤 수를 대입할지 정하지는 않았지만

(100*G + 10*C + F) + (10000*A + 1000*C + 100*D + 10*E + B)  = 

이런 식으로 계산식을 써볼 수 있을 것이다. 

위 식에서 묶을 수 있는 것들을 묶어주면 (같은 알파벳은 같은 수라고 했으므로)

10000*A + 1010*C + 100*D + 100*G + 10*E + F + B 가 될 것이다. 

이제 각 알파벳 앞에 붙어 있는 수가 큰 순서대로 9, 8, 7, 6,,, 이런 식으로 값을 대입해주면 된다. 

import java.util.*;
public class BOJ_1339_단어수학 {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String[] strArr = new String[N];
        int[] alphaArr = new int[26];
        Arrays.fill(alphaArr, 0);

        for(int i = 0; i<N; i++){
          String str = sc.next();
          //System.out.println(str);
          int len = str.length();
          for(int j = 0; j<len; j++){
              char c = str.charAt(j);   // c = 'A', 'B' ...
              alphaArr[c - 'A'] += (int)Math.pow(10, len-1-j);  //'A'면 alphaArr[0]
          }
        }

        Arrays.sort(alphaArr);
        int multipleNum = 9;
        int index = 25;
        int sum = 0;
        while(alphaArr[index]>0){
            sum += alphaArr[index] * multipleNum;
            index--;
            multipleNum--;
        }
        System.out.println(sum);
    }
}

문제

1부터 N까지의 수를 임의로 배열한 순열은 총 N! = N×(N-1)×…×2×1 가지가 있다.

임의의 순열은 정렬을 할 수 있다. 예를 들어  N=3인 경우 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}의 순서로 생각할 수 있다. 첫 번째 수가 작은 것이 순서상에서 앞서며, 첫 번째 수가 같으면 두 번째 수가 작은 것이, 두 번째 수도 같으면 세 번째 수가 작은 것이….

N이 주어지면, 아래의 두 소문제 중에 하나를 풀어야 한다. k가 주어지면 k번째 순열을 구하고, 임의의 순열이 주어지면 이 순열이 몇 번째 순열인지를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나타난다.

출력

k번째 수열을 나타내는 N개의 수를 출력하거나, 몇 번째 수열인지를 출력하면 된다.

접근 방법

주어진 시간은 2초밖에 되지 않기 때문에 노가다로 하면 시간 초과가 뜰 것이다. 

먼저 소문제 번호 = 1인 경우를 보자.

N = 5 

배열 = {1, 2, 3, 4, 5}

k = 61이라고 해보자. 

61번째 순열을 어떻게 구할 수 있을까?

먼저 61번째의 첫번째 숫자는 무엇일지 생각해보자. 2*4! < 61 < 3*4! 이므로 첫번째 숫자는 3이다.

1 _ _ _ _  => 4! (24) 가지가 있음

2 _ _ _ _ => 4! (24) 가지가 있음

3 _ _ _ _ => 4! (24) 가지가 있음

이런 방식을 활용해보면 처음 61에서 24씩 빼면서 경계를 찾아 나가다가 

61 - 24 = 37

37 - 24 = 13

13 - 24 < 0 가 됨. 24를 세번째 뺀 것이므로 세번째 범위에 답이 있고 처음 숫자는 3이 되는 것이다. 

그 다음을 보자. 우선 3은 가장 앞자리로 고정이 되었기 때문에 제외하고 1, 2, 4, 5 가 남았다. 

3, 1, _ _ _ => 3! (6) 가지가 있음 (49 ~ 54)

3, 2, _ _ _ => 3! (6) 가지가 있음 (55 ~ 60) 

3, 4, _ _ _ => 3! (6) 가지가 있음 (61 ~ 66)- > 이 중에 61번째 순열이 있음 

3, 5, _ _ _ => 3! (6) 가지가 있음 (67 ~ 73)

단순하게 보면 위와 같은데, 처음에 썼던 빼기 규칙을 써보면 

13 - 6 = 7 > 0이고

7 - 6  = 1 > 0이고 

1 - 6 <0 이므로 세번째 범위에 답이 있고 두번째 숫자는 4가 되는 것이다. 

이런 식으로 계속 빼 나가면서 숫자를 지정해나가면 된다. 

다음 소문제 번호 = 2인 경우를 보자.

위에서 했던 방식을 거꾸로 하면 된다. 

N = 5일 때 61번째 순열인 {3, 4 ,1 ,2, 5} 를 보자. {3, 4, 1, 2, 5}를 보고 어떻게 61번째 순열인지 알 수 있을까?

각 자리의 숫자보다 작은 수로 시작하는 순열의 가지수를 세가면서 더하면 된다. 

1, _ _ _ _ 는 4! (24)가지

2, _ _ _ _ 도 4!(24)가지이다. 

그럼 우선 sum은 24+24 = 48이 된다. 

3은 visit 표시를 해 놓고 다음 차례인 4를 보자. 

3, 4, _ _ _ <- 이 순열의 전에는 

3, 1, _ _ _  

3, 2, _ _ _

이 두 순열이 우선이 됐을 것이다. 각각 3! (6) 가지이므로 48 + 6 + 6 = 60이 된다. 

3, 4, _ _ _ 정해졌고 남은 수는 1, 2, 5 인데 구하는게 3, 4, 1, 2, 5가 몇번째인지 구하는 것이므로 

sum 인 60에 1을 더하면 된다. 

import java.util.*;
public class BOJ_1722_순열의순서 {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long[] fac = new long[21];
        fac[0] = 1;
        for(int i = 1; i<=20 ;i++) fac[i] = i*fac[i-1];

        int N = sc.nextInt();
        int num = sc.nextInt();
        long k = 0;
        int[] arr = new int[N+1];
        boolean[] visited = new boolean[N+1];
        Arrays.fill(arr,0);
        Arrays.fill(visited,false);

        Vector<Integer> ansVec = new Vector<Integer>();
        long ans = 1;

        if (num==1){
            k = sc.nextLong();      //Long으로 입력하지 않으면 런타임 에러뜸
            for(int i = 0; i<N; i++){
                for(int j = 1; j<=N; j++){
                    if(visited[j]) continue;    //이미 사용된 숫자는 패스
                    if(k - fac[N-1-i] > 0) {    //0이랑 같으면 1 3 4 2가 오답으로 출력됨 
                        k -= fac[N-1-i];        
                    }
                    else {                         
                        ansVec.add(j);
                        visited[j] = true;
                        break;
                    }
                }
            }
            for(int i = 0; i<ansVec.size(); i++){
                System.out.print(ansVec.elementAt(i) + " ");
            }

        }
        else if (num==2){
            for(int i = 0; i<N; i++){
                arr[i] = sc.nextInt();  
            }
            for(int i = 0; i<N; i++){
                for(int j = 1; j<arr[i]; j++){      //arr[i] 보다는 작은 수가 앞에 나올 수 있으므로 
                    if(visited[j] == false){
                        ans += fac[N-1-i];
                    }

                }
                visited[arr[i]] = true;
            }
            System.out.println(ans);



        }
    }
}

문제

행의 수가 N이고 열의 수가 M인 격자의 각 칸에 1부터 N×M까지의 번호가 첫 행부터 시작하여 차례로 부여되어 있다. 격자의 어떤 칸은 ○ 표시가 되어 있다. (단, 1번 칸과 N × M번 칸은 ○ 표시가 되어 있지 않다. 또한, ○ 표시가 되어 있는 칸은 최대 한 개이다. 즉, ○ 표시가 된 칸이 없을 수도 있다.) 

행의 수가 3이고 열의 수가 5인 격자에서 각 칸에 번호가 1부터 차례대로 부여된 예가 아래에 있다. 이 격자에서는 8번 칸에 ○ 표시가 되어 있다.

격자의 1번 칸에서 출발한 어떤 로봇이 아래의 두 조건을 만족하면서 N×M번 칸으로 가고자 한다. 

• 조건 1: 로봇은 한 번에 오른쪽에 인접한 칸 또는 아래에 인접한 칸으로만 이동할 수 있다. (즉, 대각선 방향으로는 이동할 수 없다.)
• 조건 2: 격자에 ○로 표시된 칸이 있는 경우엔 로봇은 그 칸을 반드시 지나가야 한다. 

위에서 보인 것과 같은 격자가 주어질 때, 로봇이 이동할 수 있는 서로 다른 경로의 두 가지 예가 아래에 있다.

• 1 → 2 → 3 → 8 → 9 → 10 → 15
• 1 → 2 → 3 → 8 → 13 → 14 → 15

격자에 관한 정보가 주어질 때 로봇이 앞에서 설명한 두 조건을 만족하면서 이동할 수 있는 서로 다른 경로가 총 몇 개나 되는지 찾는 프로그램을 작성하라. 

입력

입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다.

출력

주어진 격자의 정보를 이용하여 설명한 조건을 만족하는 서로 다른 경로의 수를 계산하여 출력해야 한다. 

서브태스크

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.

출력

각 줄에 하나씩, 사전식으로 가능성 있는 암호를 모두 출력한다.

접근 방법

전체 입력된 C개의 문자들을 우선 사전순으로 sorting 한 뒤, 그 L개를 선택했을 때 최소 모음 1개, 자음 2개가 되면 출력하는 방식이다. 

나는 DFS로 풀었는데, dfs 함수의 인자를 start, str 두개로 지정했다.

start 인자는 dfs 함수 안의 for문을 돌 때 사용되는데

만약 이 start 인자 없이 그냥 for 문을 매번 0부터 시작해서 돌게 되면 아래와 같은 문제가 발생한다. 

acis

acit

aciw

를 출력하고 그 다음 순서는

acst인데

acsi가 출력된다. 이유는 아래 상황에서 dfs 재귀 함수가 한 턴 끝나고 나오면서 'i'의 방문 여부가 false 로 되어 있는 상황이기 때문에

a, c, s 다음에 't'가 아니라 't'보다 인덱스가 앞서고 visited가 false인 'i'가 나오는 것이다. 

arr = {a, c, i, s, t, w}  

visited = {1, 1, 0, 1, 0, 0} 

이 부분만 주의하면 정형화된 dfs 코드이니 쉽게 코드를 짤 수 있을 것이다. 

문제

농부 존은 남는 시간에 MooTube라 불리는 동영상 공유 서비스를 만들었다. MooTube에서 농부 존의 소들은 재밌는 동영상들을 서로 공유할 수 있다. 소들은 MooTube에 1부터 N까지 번호가 붙여진 N (1 ≤ N ≤ 5,000)개의 동영상을 이미 올려 놓았다. 하지만, 존은 아직 어떻게 하면 소들이 그들이 좋아할 만한 새 동영상을 찾을 수 있을지 괜찮은 방법을 떠올리지 못했다.

농부 존은 모든 MooTube 동영상에 대해 “연관 동영상” 리스트를 만들기로 했다. 이렇게 하면 소들은 지금 보고 있는 동영상과 연관성이 높은 동영상을 추천 받을 수 있을 것이다.

존은 두 동영상이 서로 얼마나 가까운 지를 측정하는 단위인 “USADO”를 만들었다. 존은 N-1개의 동영상 쌍을 골라서 직접 두 쌍의 USADO를 계산했다. 그 다음에 존은 이 동영상들을 네트워크 구조로 바꿔서, 각 동영상을 정점으로 나타내기로 했다. 또 존은 동영상들의 연결 구조를 서로 연결되어 있는 N-1개의 동영상 쌍으로 나타내었다. 좀 더 쉽게 말해서, 존은 N-1개의 동영상 쌍을 골라서 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재하도록 했다. 존은 임의의 두 쌍 사이의 동영상의 USADO를 그 경로의 모든 연결들의 USADO 중 최솟값으로 하기로 했다.

존은 어떤 주어진 MooTube 동영상에 대해, 값 K를 정해서 그 동영상과 USADO가 K 이상인 모든 동영상이 추천되도록 할 것이다. 하지만 존은 너무 많은 동영상이 추천되면 소들이 일하는 것이 방해될까 봐 걱정하고 있다! 그래서 그는 K를 적절한 값으로 결정하려고 한다. 농부 존은 어떤 K 값에 대한 추천 동영상의 개수를 묻는 질문 여러 개에 당신이 대답해주기를 바란다.

입력

입력의 첫 번째 줄에는 N과 Q가 주어진다. (1 ≤ Q ≤ 5,000)

다음 N-1개의 줄에는 농부 존이 직접 잰 두 동영상 쌍의 USADO가 한 줄에 하나씩 주어진다. 각 줄은 세 정수 pi, qi, ri (1 ≤ pi, qi ≤ N, 1 ≤ ri ≤ 1,000,000,000)를 포함하는데, 이는 동영상 pi와 qi가 USADO ri로 서로 연결되어 있음을 뜻한다.

다음 Q개의 줄에는 농부 존의 Q개의 질문이 주어진다. 각 줄은 두 정수 ki와 vi(1 ≤ ki ≤ 1,000,000,000, 1 ≤ vi ≤ N)을 포함하는데, 이는 존의 i번째 질문이 만약 K = ki라면 동영상 vi를 보고 있는 소들에게 몇 개의 동영상이 추천될 지 묻는 것이라는 것을 뜻한다.

출력

Q개의 줄을 출력한다. i번째 줄에는 농부 존의 i번째 질문에 대한 답변이 출력되어야 한다.

힌트

농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 USADO는 min(3,2)=2가 되고, 1번 동영상과 4번 동영상의 USADO는 min(3,4)=3이 되고, 3번 동영상과 4번 동영상의 USADO는 min(2,4)=2가 된다.

농부 존은 K=1일 때 2번 동영상, K=3일 때 1번 동영상, K=4일 때 1번 동영상을 보면 각각 몇 개의 동영상이 추천될까 궁금해하고 있다. K=1일 때 2번 동영상에서 추천되는 동영상은 1, 3, 4번 동영상이다. K=4일 때 1번 동영상으로부터 추천되는 동영상은 없다. 그러나 K=3일때는 1번 동영상에서 2번 동영상과 4번 동영상이 추천된다.

접근 방법

처음에는 노드간 모든 pair에 대해, a->b 노드로 가는 edge의 min을 구해서 a, b 노드 간의 usado를 처음부터 다 구해놓으려고 했었다. 

이 방법은 너무 비효율적일 것 같아서 각 Question마다 주어지는 k와 v에 대해서만 확인해서 그때그때 답을 구하는 것이 좋을것 같았다. 

그러기 위해 각각 연결된 노드들의 정보들만 저장하는 리스트 graphList를 생성했다. 

graphList[1]에는 1번 노드와 연결된 모든 노드와, 그 노드까지의 edge 정보를 저장해놓는다. (그 정보는 Node 객체에 넣어서 저장한다)

위 예제로 예시를 들면 graphList에 담긴 정보는 아래와 같다. 

graphList[1] => (2,3)

graphList[2] => (1,3), (3,2), (4,4)

graphList[3] => (2, 2)

graphList[4] => (2, 4)

그래서 매 Question마다 bfs를 도는데, graphList[현재노드] 의 크기만큼 돌게 되며(시작 노드와 다이렉트로 연결된 노드 모두 방문해가면서), 다이렉트로 연결되지 않은 노드에 대해서도 que.add를 통해 탐색 대상에 넣어 탐색을 하게 된다. 

import java.util.*;
public class BOJ_15591_MoonTube {
    static class Node{
        int node, weight;
        public Node(int n, int w){
            this.node = n;
            this.weight = w;
        }
    }

    static int bfs(int k, int v, ArrayList<ArrayList<Node>> graphList, int N){
        int[] visited = new int[N+1]; //노드번호 1부터 ~ N까지이므로 N+1개
        int cntVideo = 0;
        Queue<Integer> que = new LinkedList<Integer>();
        que.add(v);   //시작 노드
        visited[v] = 1;

        while(!que.isEmpty()) { //방문할 노드가 없을 때까지
            int curNode = que.poll();

            for(int i = 0; i<graphList.get(curNode).size(); i++){
                int w = graphList.get(curNode).get(i).weight;   //usado
                int n = graphList.get(curNode).get(i).node;
                if(w<k || visited[n] != 0) {continue;}    //문제에서 weight가 k이상일 때만 (w>=k)물어봄, w<k인 케이스는 패스

                que.add(n);     //다음 방문할 노드 저장. v노드와 다이렉트로 연결되지 않은 노드에 대해서도 탐색 가능 
                visited[n] = 1;
                cntVideo++;

            }
        }
        return cntVideo;
    }

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int Q = sc.nextInt();
        ArrayList<ArrayList<Node>> graphList = new ArrayList<ArrayList<Node>>();    //graphList[x]에는 x 노드와 연결된 노드의 정보와 간선 정보가 객체로 들어있다.
        for(int i = 0; i<=N; i++){//노드 1~N까지 있으므로
            graphList.add(new ArrayList<Node>());
        }
        for(int i = 1; i<=N-1; i++){
            int p = sc.nextInt();
            int q = sc.nextInt();
            int r = sc.nextInt();
            //그래프 정보 입력. 간선에 연결된 노드 양쪽에 대해 각각 정보 입력
            graphList.get(p).add(new Node(q,r));
            graphList.get(q).add(new Node(p,r));
        }
        ArrayList<Integer> ansList = new ArrayList<Integer>();
        for(int i = 1; i<=Q; i++){
            int k = sc.nextInt();
            int v = sc.nextInt();
            int ans = bfs(k, v, graphList, N);
            ansList.add(ans);
        }
        for(int i = 0; i<ansList.size(); i++){
            System.out.println(ansList.get(i));
        }



    }
}

참고 : https://fjvbn2003.tistory.com/873