CodeDrive

문제:

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

출력:

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

풀이방법:

 수학 시간에 배웠던 경로의 갯수 공식을 사용하도록 한다. 사각형이 있고, 되돌아 갈 수 없다는 조건이 있다면 시작점에서 도착점까지 가는 경우의 수는 (가로변의 갯수 + 세로변의 갯수)C(가로변의 갯수 or 세로변의 갯수)다. 이 문제의 경우 격자에 하나의 중심점이 표현되어 있기 때문에, 이 점을 기준으로 두 번의 경우의 수를 구한 다음에 둘을 곱하면 최종 답을 얻을 수 있다.

 따라서 이 문제는 O 표시가 되어 있는 지점의 좌표를 정확하게 계산하고, combination 연산 공식을 구현하여 문제를 해결하면 된다.

문제링크:

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

문제:

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개의 수를 출력하거나, 몇 번째 수열인지를 출력하면 된다.

풀이방법:

 한 문제에 K번째 수열을 구하는 문제와 주어진 수열이 몇 번째인지 구하는 문제가 합쳐져 있다. 두 소문제는 주어진 수 중 맨 앞의 숫자로 구별되며, 이를 command(c)로 구분해 각 소문제를 풀도록 한다.

 첫 번째 소문제는 K번째 수열을 구하는 문제다. 앞의 자릿수부터 계산하며, 주어진 수 K로부터 만들 수 있는 경우의 수를 빼주며 한자리씩 정해나간다. 즉, 예제의 경우 3번째 수열을 구하는 문제에서 맨 앞자리를 a인 경우의 수는 3!개이다. 따라서 3번째 수열은 0~3!번째 수열에 속할 것이므로, 맨 앞자리는 1인 것을 알 수 있다. 이러한 방법을 계속하여 k번째 수열을 찾는다.

 두 번째 소문제는 첫 번째 소문제의 역으로 구할 수 있다. 팩토리얼을 사용해 k번째 수열을 구했던 것의 역으로 팩토리얼을 더하면서 k를 찾도록 한다.

문제링크:

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

문제:

윤영이는 3의 배수 마니아이다. 그는 모든 자연수를 3개의 3의 배수의 자연수로 분해하는 것을 취미로 가지고 있다. 문득 그는 자신에게 주어진 수를 3개의 3의 배수로 분리하는 경우의 수가 몇 개인지 궁금해졌다. 하지만 윤영이는 마지막 학기이기 때문에 이런 계산을 하기에는 너무 게을러졌다. 그래서 당신에게 이 계산을 부탁했다.

즉, 임의의 3의 배수 자연수 n이 주어졌을 때, 해당 수를 3의 배수의 자연수 3개로 분리하는 방법의 개수를 출력해라. 단, 분해한 수의 순서가 다르면 다른 방법으로 간주한다. 예를 들어 12 = 3+6+3과 12=3+3+6은 다른 방법이다.

입력:

임의의 3의 배수 자연수 n이 주어진다. (3<=n<=3000)

출력:

자연수 n을 분해하는 방법의 개수를 출력하라.

풀이방법:

고등학교 수학이 생각나는 문제다. 이 문제를 변수로 나타내면 x+y+z = n (x,y,z,n은 3의 배수) 와 같고, 이는 조합 문제와 동일하다.

1. 간결하게 표현하기 위해 모든 수가 3의 배수이므로 3으로 나눠준다. (x'+y'+z' = n//3, x',y',z'>=0)

2. 3의 배수의 자연수로 분해를 해야 하기 때문에 좌변에 3을 빼줌으로써 해결한다. (x''+y''+z'' = n//3-3, x''+y''+z''>=1), 이는 nHr을 계산하는 문제와 같아진다.(3Hn//3-3)

따라서 이를 계산하면 답을 구할 수 있다.

문제링크:

www.acmicpc.net/problem/16561