728x90
728x90

문제 링크 : https://acmicpc.net/problem/15989

 

15989번: 1, 2, 3 더하기 4

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

www.acmicpc.net

 

문제

정수 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의 합으로 나타내는 방법의 수를 출력한다.

 

예제 입력 1 

3
4
7
10

예제 출력 1 

4
8
14

 

풀이 방법

[1]

1

=> 1가지

(0가지 일 수도 있는지?...)

 

[2] 

1 + 1

=> 1가지

 

[3]

1 + 1 + 1

2 + 1

=> 2가지

 

[4]

1 + 1 + 1 + 1

2 + 1 + 1 , 2 + 2

3 + 1

=> 4가지

 

[5]

1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 , 2 + 2 + 1

3 + 1 + 1, 3 + 2

=> 5가지

 

[6]

1 + 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 , 2 + 2 + 1 + 1, 2 + 2 + 2

3 + 1 + 1 + 1, 3 + 2 + 1

3 + 3

=> 7가지

 

[7]

1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 + 1 , 2 + 2 + 1 + 1 + 1, 2 + 2 + 2 + 1

3 + 1 + 1 + 1 + 1, 3 + 2 + 1 + 1, 3 + 2 + 2, 

3 + 3 + 1

=> 8가지

 

[8]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1), (2 + 2 + 2+ 2)

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

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

=> 10가지

 

 [9]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1)

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

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

(3 + 3 + 3)

=> 12가지

 

 [10]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1 + 1), (2 + 2 + 2+ 2 + 2)

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

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

(3 + 3 + 3 + 1)

=> 14가지

 

 [11]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 2 + 1)

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

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

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

=> 16가지

 

0 1 2 3 4 5 6 7 8 9 10
0 0 1 2 4 5 6 8 10 12 14

 

 

6부터 2씩 증가-> fail!!!

 

 

==========================

dp[n,k] : 1,,,k 를 활용해 n을 만드는 방법의 수로 가정하고 각 값을 구해보자. 

===========================================

dp[n,1]을 구해보자. 

 

 

dp[n,2]을 구해보자. 

dp[n,3]을 구해보자. 

1 1 dp[1,2] : 1, 2을 활용해 1을 만드는 방법의 수
1
1 dp[1,3] : 1, 2, 3을 활용해 1을 만드는 방법의 수
1
1
1 + 1 1 dp[2,2]  : 1, 2를 활용해 2을 만드는 방법의 수
1 + 1
1 dp[2,3] : 1, 2, 3을 활용해 2을 만드는 방법의 수
1 + 1
2
2
1 + 1 + 1 1 dp[3,2] : 1, 2를 활용해 3을 만드는 방법의 수
1 + 1 + 1
2 + 1
2 = dp[3,1] + 1 dp[3,3] : 1, 2, 3을 활용해 3을 만드는 방법의 수
1 + 1 + 1
2 + 1
3
3
1 + 1 + 1 + 1 1 dp[4,2] : 1, 2를 활용해 4를 만드는 방법의 수
1 + 1 + 1 + 1
2 + 1 + 1
2 + 2
3 = dp[4,1] + 2 dp[4,3] : 1, 2, 3을 활용해 4을 만드는 방법의 수
1 + 1 + 1 + 1
2 + 1 + 1
2+ 2
3 + 1
4 = dp[4,2] + 1
1 + 1 + 1 + 1 + 1 1 dp[5,2] : 1, 2를 활용해 5를 만드는 방법의 수
1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1
2 + 2 + 1
3 = dp[5,1] + 2 dp[5,3] : 1, 2, 3을 활용해 5을 만드는 방법의 수
1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1
2+ 2 + 1
3 + 1 + 1
3 + 2
5 = dp[5,2] + 2
1 + 1 + 1 + 1 + 1 + 1 1 dp[6,2] : 1, 2를 활용해 6을 만드는 방법의 수
1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1
2 + 2 + 1 + 1
2 + 2 + 2
4 = dp[6,1] + 3 dp[6,3] : 1, 2, 3을 활용해 6을 만드는 방법의 수
1 + 1 + 1 + 1 + 1 + 1 
2 + 1 + 1 + 1 + 1 
2 + 2 + 1 + 1  
2 + 2 + 2
3 + 1 + 1 + 1
3 + 2 + 1
3 + 3
7 = dp[6,2] + 3
1 + 1 + 1 + 1 + 1 + 1 + 1 1 dp[7,2] : 1, 2를 활용해 7을 만드는 방법의 수
1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1
2 + 2 + 1 + 1 + 1
2 + 2 + 2 + 1
4 = dp[7,1] + 3 dp[7,3] : 1, 2, 3을 활용해 7을 만드는 방법의 수
1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1 
2 + 2 + 1 + 1 + 1
2 + 2 + 2 + 1
3 + 1 + 1 + 1 + 1
3 + 2 + 1 + 1
3 + 2 + 2
3 + 3 + 1
8 = dp[7,2] + 4
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 1 dp[8,2] : 1, 2를 활용해 8을 만드는 방법의 수
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1 + 1
2 + 2 + 1 + 1 + 1 + 1
2 + 2 + 2 + 1 + 1
2 + 2 + 2 + 2
5 = dp[8,1] + 4 dp[8,3] : 1, 2, 3을 활용해 8을 만드는 방법의 수
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1 + 1
2 + 2 + 1 + 1 + 1 + 1
2 + 2 + 2 + 1 + 1
2 + 2 + 2 + 2
3 + 1 + 1 + 1 + 1 + 1
3 + 2 + 1 + 1 + 1
3 + 2 + 2 + 1
3 + 3 + 1 + 1
3 + 3 + 2
10 = dp[8,2] + 5
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 1 dp[9,2] : 1, 2를 활용해 9을 만드는 방법의 수
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 2 + 1 + 1 + 1 + 1 + 1
2 + 2 + 2 + 1 + 1 + 1
2 + 2 + 2 + 2 + 1
5 = dp[9,1] + 4 dp[9,3] : 1, 2, 3을 활용해 9을 만드는 방법의 수
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 2 + 1 + 1 + 1 + 1 + 1
2 + 2 + 2 + 1 + 1 + 1
2 + 2 + 2 + 2 + 1

3 + 1 + 1 + 1 + 1 + 1 + 1
3 + 2 + 1 + 1 + 1 + 1
3 + 2 + 2 + 1 + 1
3 + 2 + 2 + 2

3 + 3 + 1 + 1 + 1
3 + 3 + 2 + 1
3 + 3 + 3
12  = dp[9,2] + 7
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 1 dp[10,2] : 1, 2를 활용해 10을 만드는 방법의 수
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 2 + 1 + 1 + 1 + 1 + 1 + 1
2 + 2 + 2 + 1 + 1 + 1 + 1
2 + 2 + 2 + 2 + 1 + 1
2 + 2 + 2 + 2 + 2
6 = dp[10,1] + 5 dp[10,3] : 1, 2, 3을 활용해 10을 만드는 방법의 수
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 2 + 1 + 1 + 1 + 1 + 1 + 1
2 + 2 + 2 + 1 + 1 + 1 + 1
2 + 2 + 2 + 2 + 1 + 1
2 + 2 + 2 + 2 + 2
3 + 1 + 1 + 1 + 1 + 1 + 1 + 1
3 + 2 + 1 + 1 + 1 + 1 + 1
3 + 2 + 2 + 1 + 1 + 1
3 + 2 + 2 + 2 + 1

3 + 3 + 1 + 1 + 1 + 1
3 + 3 + 2 + 1 + 1
3 + 3 + 2 + 2
3 + 3 + 3 + 1
14 = dp[10,2] + 8
           
    dp[15,2]
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2 + 2 + 2+ 1 + 1 + 1

2 + 2 + 2 + 2 + 2 + 2+ 2+ 1

8 = dp[15,1] + 14 dp[15,3]
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2 + 2 + 2+ 1 + 1 + 1

2 + 2 + 2 + 2 + 2 + 2+ 2+ 1

======
3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
3 + 2 + 1 + 1 + 1 + 1 + 1 + 1
3 + 2 + 2 + 1 + 1 + 1 + 1
3 + 2 + 2 + 2 + 1 + 1
3 + 2 + 2 + 2 + 2

3 + 3 + 1 + 1 + 1 + 1 + 1
3 + 3 + 2 + 1 + 1 + 1
3 + 3 + 2 + 2 + 1
3 + 3 + 3 + 1 + 1
3 + 3 + 3 + 2
18
    dp[20,2]
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2 + 2 + 2+ 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2 + 2 + 2+ 2+ 1 + 1 + 1 + 1 + 1 + 1


2 + 2 + 2 + 2 + 2 + 2+ 2+ 2 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2 + 2 + 2+ 2+ 2 + 2 + 1 + 1

2 + 2 + 2 + 2 + 2 + 2+ 2+ 2 + 2+ 2
11 dp[20,3]
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2 + 2 + 2+ 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2 + 2 + 2+ 2+ 1 + 1 + 1 + 1 + 1 + 1


2 + 2 + 2 + 2 + 2 + 2+ 2+ 2 + 1 + 1 + 1 + 1

2 + 2 + 2 + 2 + 2 + 2+ 2+ 2 + 2 + 1 + 1

2 + 2 + 2 + 2 + 2 + 2+ 2+ 2 + 2+ 2
==============
3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
3 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1
3 + 2 + 2 + 1 + 1 + 1 + 1 + 1
3 + 2 + 2 + 2 + 1 + 1 + 1
3 + 2 + 2 + 2 + 2 + 1

3 + 3 + 1 + 1 + 1 + 1 + 1 + 1
3 + 3 + 2 + 1 + 1 + 1 + 1
3 + 3 + 2 + 2 + 1 + 1
3 + 3 + 2 + 2 + 2

3 + 3 + 3 + 1 + 1 + 1
3 + 3 + 3 + 2 + 1
3 + 3 + 3 + 3
 

 

  • dp[n,1] = 1
  • dp[n,2] = n/2(몫만) + 1
  • dp[n-3] = dp[n-1, 1] +dp[n-2, 2] + dp[n-3, 3]   = 1 + {(n-2)/2} + 1 + dp[n-3,3]
import java.util.Scanner;

public class BOJ_15989_123더하기4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int[][] dp= new int[10001][4];

        for(int n = 0; n<=10000; n++){
            dp[n][0] = 0;
            dp[n][1] = 1;
            dp[n][2] = n/2 + 1;
        }
        dp[1][2] = 1; dp[1][3] = 1;
        dp[2][2] = 1; dp[2][3] = 2;
        dp[3][2] = 2; dp[3][3] = 3;
        dp[4][2] = 3; dp[4][3] = 4;
        
        for(int i = 5; i<=10000; i++){
            dp[i][3] = 2 + (i-2)/2 + dp[i-3][3];
        }


        int n;
        for(int i = 0; i<T; i++){
            n = sc.nextInt();
            System.out.println(dp[n][3]);

        }
    }
}

 

 

 

 

728x90
728x90

문제 링크 : https://www.acmicpc.net/problem/1339

 

1339번: 단어 수학

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

www.acmicpc.net

 

문제

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

단어 수학 문제는 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);
    }
}

 

 

 

참고  : https://mountain96.tistory.com/21

728x90
728x90

문제 링크 : https://www.acmicpc.net/problem/1722

 

1722번: 순열의 순서

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

www.acmicpc.net

 

문제

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);



        }
    }
}

 

 

728x90
728x90

문제 링크 : https://www.acmicpc.net/problem/10164

 

10164번: 격자상의 경로

입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으

www.acmicpc.net

문제

행의 수가 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인 경우는 없다.

출력

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

서브태스크

번호배점제한
1 9 1 ≤ N, M ≤ 5, K = 0
2 24 1 ≤ N, M ≤ 5, 1 < K < N × M
3 23 1 ≤ N, M ≤ 15, K = 0
4 44 원래의 제약조건 이외에 아무 제약조건이 없다.

 


접근 방법

처음에는 조합으로 풀었다가 32점이 나와서 dp로 문제를 해결했다.

 

 

처음 접근 방법은 K가 0이 아니면

K의 좌표를 구한 다음 -> 그 좌표까지 가려면 우측 방향으로 몇번 가야하는지와 아래 방향으로 몇 번 가야하는지를 조합을 사용해서 계산햇다. 

예제를 예시로 들면 아래에서 K까지 가려면 처음 [0][0]에서 우측으로 두 번, 아래 방향으로 한 번 가면 되는 것이다.

총 세번 이동을 해야하는데 그 중에 아래 화살표들을 순서 상관 없이 나열하는 조합의 경우의 수를 구하면 된다. 

➡️➡️⬇️

➡️⬇️➡️

⬇️➡️➡️

 

import java.util.Scanner;

public class Main {

    static int combi(int n, int r){
        if(n==r || r==0) return 1;
        return combi(n-1, r-1) + combi(n-1,r);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int K = sc.nextInt();
        int ans = 0;

        if(K!=0){
            int kRow = K/M;
            int kCol = K%M -1;

            int first = combi(kRow+kCol, kCol);
            int second = combi(M-kCol-1 + N-kRow-1, N-kRow-1);
            ans = first*second;
        }
        else{
            ans = combi(N+M-2, N-1);
        }
        System.out.println(ans);

    }
}

 

 

그러나 이 방법으로는 32점밖에 안 나와서 N,M이 커지면 서브테스크 3번부터 막히는 것 같아 dp로 다시 풀었다.

dp로 풀때 주의할 점은 K의 위치를 잘 구해야 한다는 것이다.

예제로 주어진 문제로만 푸는 것이 아니라

반레로 K가 M으로 딱 나눠서 떨어지는 경우 즉 입력 값이 (2, 2, 2) 인 케이스도 생각하면 서브 테스크 3,4번도 모두 맞출 수 있다

import java.util.Scanner;

public class BJOJ_10164_격자상의경로 {

    static int combi(int n, int r){
        if(n==r || r==0) return 1;
        return combi(n-1, r-1) + combi(n-1,r);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int K = sc.nextInt();
        int ans = 0;
        int[][] dp = new int[N][M];
        dp[0][0] = 0;

        if(K!=0){
            int kRow = K/M;
            int kCol = K%M;
            if(K%M == 0) {		//K가 오른쪽 끝에 붙어있는 경우 고려
                kRow -= 1;
                kCol = M-1;
            }else kCol-=1;


            for(int i = 1; i<=kRow; i++) {
                dp[i][0] = 1;
            }
            for(int i = 1; i<=kCol; i++){
                dp[0][i] = 1;
            }
            for(int i = 1; i<=kRow; i++){
                for(int j = 1; j<=kCol; j++){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
            for(int i = kRow+1; i<N; i++) dp[i][kCol] = dp[kRow][kCol];
            for(int j = kCol+1; j<M; j++) dp[kRow][j] = dp[kRow][kCol];
            for(int i = kRow+1; i<N; i++){
                for(int j = kCol+1; j<M; j++){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }

        }
        else{
            for(int i = 1; i<N; i++) {
                dp[i][0] = 1;
            }
            for(int i = 1; i<M; i++){
                dp[0][i] = 1;
            }
            for(int i = 1; i<N; i++){
                for(int j = 1; j<M; j++){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        System.out.println(dp[N-1][M-1]);


    }
}

 

 

728x90
728x90

문제 링크 : https://www.acmicpc.net/problem/1759

 

1759번: 암호 만들기

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

www.acmicpc.net

문제

바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 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 코드이니 쉽게 코드를 짤 수 있을 것이다. 

 

import java.util.*;

public class BOJ_1759_암호만들기 {

    static boolean[] visited;
    static char[] arr;
    static int L, C;
    static boolean chk(String str){
        int cnt1 = 0; //모음
        int cnt2 = 0; //자음
        for(int i = 0; i<str.length(); i++){
            if(str.charAt(i)=='a' || str.charAt(i)=='e' || str.charAt(i)=='i' || str.charAt(i)=='o' || str.charAt(i)=='u'){
                cnt1++;
            }
            else cnt2++;
            if(cnt1>=1 && cnt2>=2) return true;
        }
        return false;
    }

    static void dfs(int start, String str){
        if(str.length()==L){
            if(chk(str)){
                System.out.println(str);
                return;
            }

        }
        for(int i = start; i<C; i++){
            if(visited[i]==false){
                str = str + arr[i];
                visited[i] = true;
                dfs(i+1, str);
                str = str.substring(0, str.length()-1);
                visited[i] = false;
            }
        }


    }



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

        L = sc.nextInt();
        C = sc.nextInt();
        arr = new char[C];
        visited = new boolean[C];


        for(int i = 0; i<C; i++){
            arr[i] = sc.next().charAt(0);
            visited[i] = false;
        }
        Arrays.sort(arr);
        String initStr = "";

        dfs(0, initStr);

    }
}

728x90
728x90
 

문제

정보문화진흥원 정보 영재 동아리에서 동아리 활동을 하던 영수와 민혁이는 쉬는 시간을 틈타 숫자야구 게임을 하기로 했다.

  • 영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. (예: 324)
  • 민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 영수에게 묻는다. (예: 123)
  • 민혁이가 말한 세 자리 수에 있는 숫자들 중 하나가 영수의 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번으로 센다. 숫자가 영수의 세 자리 수에 있긴 하나 다른 자리에 위치하면 볼 한 번으로 센다.

예) 영수가 324를 갖고 있으면 

  • 429는 1 스트라이크 1 볼이다.
  • 241은 0 스트라이크 2 볼이다.
  • 924는 2 스트라이크 0 볼이다.
  • 영수는 민혁이가 말한 수가 몇 스트라이크 몇 볼인지를 답해준다.
  • 민혁이가 영수의 세 자리 수를 정확하게 맞추어 3 스트라이크가 되면 게임이 끝난다. 아니라면 민혁이는 새로운 수를 생각해 다시 영수에게 묻는다.

현재 민혁이와 영수는 게임을 하고 있는 도중에 있다. 민혁이가 영수에게 어떤 수들을 물어보았는지, 그리고 각각의 물음에 영수가 어떤 대답을 했는지가 입력으로 주어진다. 이 입력을 바탕으로 여러분은 영수가 생각하고 있을 가능성이 있는 수가 총 몇 개인지를 알아맞혀야 한다.

아래와 같은 경우를 생각해보자.  

  • 민혁: 123
  • 영수: 1 스트라이크 1 볼.
  • 민혁: 356
  • 영수: 1 스트라이크 0 볼.
  • 민혁: 327
  • 영수: 2 스트라이크 0 볼.
  • 민혁: 489
  • 영수: 0 스트라이크 1 볼.

이때 가능한 답은 324와 328, 이렇게 두 가지이다.

영수는 동아리의 규율을 잘 따르는 착한 아이라 민혁이의 물음에 곧이곧대로 정직하게 답한다. 그러므로 영수의 답들에는 모순이 없다.

민혁이의 물음들과 각각의 물음에 대한 영수의 답이 입력으로 주어질 때 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트라이크 개수를 나타내는 정수와 볼의 개수를 나타내는 정수, 이렇게 총 세 개의 정수가 빈칸을 사이에 두고 주어진다.

출력

첫 줄에 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력한다.

예제 입력 1 

4
123 1 1
356 1 0
327 2 0
489 0 1

예제 출력 1 

2
 

 

 


접근 방법

완전 탐색으로 접근했다. 

답이 될 수 있는 숫자 조건은 000 ~ 999 중에 아래 두 조건을 만족해야 한다.  만족하지 않으면 배열 값을 -1 로 표시한다. 

1) 모두 다른 숫자로 구성되어 있어야 함

2) 숫자에 0이 들어가면 안됨

 

그 후 반복문을 돌면서 스트라이크, 볼 갯수를 카운트하고

카운트 한 스트라이크, 볼 갯수가 처음에 입력한 스트라이크/볼 수와 일치하면

그 인덱스의 배열 값을 +1 한다. (ex. 처음 입력한 숫자가 123 1 1 이고, 비교 대상이 324이면 1strike, 1ball을 만족하므로 arr[324]++)

 

그리고 마지막에 arr[i]의 값이 N과 동일하면, 즉 N번을 물어봤기 때문에 그 물어본 횟수만큼 테스트를 통과했으면(스트라이크, 볼 갯수가 일치했으면) 그 i는 후보가 된다. 그 i가 몇개인지 카운트 하면 이 문제의 답을 구할 수 있다. 

 

 

 

[반례]

 

입력
2
123 0 0
456 0 0


정답
6

import java.util.*;

public class BOJ_2503_숫자야구 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int ans = 0;

//        Integer[] arr = new Integer[1000];
        int[] arr = new int[1000];
        for (int i = 123; i <= 987; i++) {  //서로 다른 숫자 세개로 구성하므로
            String str = Integer.toString(i);   //각 자리수 비교하기 위해 형변환

            if (str.charAt(0) == str.charAt(1) || str.charAt(0) == str.charAt(2) || str.charAt(1) == str.charAt(2)
                ||str.charAt(0)=='0' || str.charAt(1)=='0' ||str.charAt(2)=='0') {  //서로 다른 숫자로 구성되지 않았으면 -1로 지정
                arr[i] = -1;
            }
        }
        //ArrayList<String> strNumList = new ArrayList<>();
        String strNum;
        //ArrayList<Integer> strikeList = new ArrayList<>();
        //ArrayList<Integer> ballList = new ArrayList<>();
        int strike;
        int ball;
        for (int i = 1; i <= N; i++) {       //N : 민혁이가 영수에게 질문한 횟수
            strNum = sc.next();
            //strNumList.add(strNum);
            strike = sc.nextInt();
            //strikeList.add(strike);
            ball = sc.nextInt();
            //ballList.add(ball);

            int strikeCnt = 0;
            int ballCnt = 0;

            for (int idx = 123; idx <= 987; idx++) {    //반복문 돌면서 strike, ball 검사
                if (arr[idx] == -1) continue;
                //System.out.print(arr[idx] + " ");
                int passCnt = 0;
                //strike 검사
                strikeCnt = 0;
                String strIdx = Integer.toString(idx);
                for (int j = 0; j < 3; j++) {
                    if (strNum.charAt(j) == strIdx.charAt(j)) strikeCnt++;
                }

                //strike 수는 맞았으니 Ball 검사
                ballCnt = 0;
                for (int p = 0; p < 3; p++) {
                    for (int q = 0; q < 3; q++) {
                        if ((strNum.charAt(p) == strIdx.charAt(q)) && (p != q)) {
                            ballCnt++;
                        }
                    }
                }
                if ((strike != strikeCnt) || ball != ballCnt) {
                    arr[idx] = -1;
                    continue;
                }

				//통과된 횟수 카운트
                if ((strike == strikeCnt) && (ball == ballCnt)) {
                    arr[idx]++;
                }
            }

        }

        for (int i = 123; i <= 987; i++) {

            if (arr[i] != -1 && arr[i] == N) {	//물어본 횟수만큼 다 만족했으면 그 숫자는 답
                ans++;
               // System.out.println(i);
            }
        }
        System.out.println(ans);

    }
}

728x90
728x90

문제 링크 : https://www.acmicpc.net/problem/15591

 

15591번: MooTube (Silver)

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

www.acmicpc.net

 

문제

농부 존은 남는 시간에 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 

4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1

예제 출력 1 

3
0
2

힌트

농부 존은 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

 

728x90
728x90

문제 링크 : https://www.acmicpc.net/problem/1484

 

1484번: 다이어트

성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다.

www.acmicpc.net

 

문제

성원이는 다이어트를 시도중이다. 성원이는 정말 정말 무겁기 때문에, 저울이 부셔졌다. 성원이의 힘겨운 다이어트 시도를 보고만 있던 엔토피아는 성원이에게 새로운 저울을 선물해 주었다. 성원이는 엔토피아가 선물해준 저울 위에 올라갔다. “안돼!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! G 킬로그램이나 더 쪘어ㅜㅠ”라고 성원이가 말했다. 여기서 말하는 G킬로그램은 성원이의 현재 몸무게의 제곱에서 성원이가 기억하고 있던 몸무게의 제곱을 뺀 것이다.

성원이의 현재 몸무게로 가능한 것을 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 G가 주어진다. G는 100,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우는 제외해야 한다.

예제 입력 1 

15

예제 출력 1 

4
8
 

접근 방법

이 문제는 보통 투포인터로 많이 푸는 문제이다. 즉, G = (현재+기억)*(현재-기억) 인 점을 활용하여 현재 몸무게와 기억하는 몸무게 간의 관계를 바탕으로 정해진 범위 내에서 몸무게 2개를 조절해가면서(투포인터) 수식을 만족하는 현재 몸무게를 찾는 방식이다. 

 

나는 G = (현재+기억)*(현재-기억) 에서 

  • a = 현재+기억
  • b = 현재-기억

a+b  = 2*(현재) 이므로 a+b는 짝수

인 점을 활용했다. 

 

탐색 범위는 a가 1부터(현재, 기억 모두 자연수이므로 2부터 해도 됨) G까지 했다.

G까지 한 이유는 다음과 같다.

현재와 기억의 최소 차이를 생각해봤을 때 b = 현재-기억 은 양수이므로 현재와 기억 몸무게의 최소 차이는 1이다. 이 경우를 조건의 끝이라고 생각하면 G = a가 된다. 

 

추가로

1) b = G/a인 점

2) a와 b 모두 양수인 점(a와 b를 곱해서 G가 나와야하며 G는 자연수이므로)

3) 현재 몸무게가 자연수이고, 기억하는 몸무게도 자연수인 점(13번째 line에서 a<=b가 아닌 a<b로 하면 오답으로 나온다. 즉 a>=b인 경우를 고려하면 틀린다는 소리이며 그 중 a=b인 경우가 오답의 원인이 되는 것이다. 아래 링크도 추가 참고하면 기억하는 몸무게도 자연수로 고려해야하는 것 같다.)

 

https://www.acmicpc.net/board/view/115572

 

글 읽기 - 문제 내용 추가 요청입니다.

댓글을 작성하려면 로그인해야 합니다.

www.acmicpc.net

 

 

아래 반례가 도움이 되었다. 

https://www.acmicpc.net/board/view/99783

 

글 읽기 - 1484. 다이어트 질문입니다.

댓글을 작성하려면 로그인해야 합니다.

www.acmicpc.net

import java.util.*;

public class BOJ_1484_다이어트 {

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        TreeSet<Integer> set = new TreeSet<Integer>();

        int G = sc.nextInt();
        for(int a = 1; a<=G; a++){	//a 탐색 범위를 1부터 G까지 해야함.
            if(G%a != 0) continue;		//b가 G의 약수가 아니면 패스
            int b = G / a;				//b는 G의 약수 
            if(((a+b) % 2 != 0) || (a<=b)) continue;	//짝수가 아니거나 범위 벗어나면 패스
            set.add((a+b)/2);
        }
        if(set.size() == 0){
            System.out.println(-1);
        }

        else{
            Iterator iter = set.iterator();
            while(iter.hasNext()){
                System.out.println(iter.next());
            }
        }
    }
}

 

728x90

+ Recent posts