Homework 1 Solution

Description

1. 모든 프로그램은 윈도우 명령 프롬프트에서 수행이 가능하여야 함. (즉, console programming).

2. 모든 입출력은 stdin과 stdout을 사용하고 re-direction을 통하여 파일을 읽거나 생성.

.

문제 1. 로마숫자 표기법 및 덧셈하기

로마숫자는 I=1, V=5, X=10, L=50, C=100, D=500, M=1000을 기본적으로 사용한다. 이러한 7 개의 문자로 다음과 같은 규칙에 의하여 수를 표기한다.

1. 우리가 일반적으로 사용하는 숫자와는 달리 ‘자리’라는 개념이 없이 주어진 숫자문자들을 모두 더하여 그 값을 구한다. 예를 들어 LX=60, CCL=250이다.

2. 숫자는 일반적으로 그 값이 큰 수부터 작은 수 순으로 표기한다. 그러나 어떤 숫자의 왼쪽에 그보다 작은 숫자가 있으면 큰 수에서 작은 수를 뺀다. 그런데 이 규칙은 큰 수 왼쪽 한 자리 수에만 해당한다. 예를 들어, IV=4, IX=9이지만 IIX는 허용되지 않는다.

3. 로마 숫자의 다양한 예를 보이면 다음과 같다: 1= I, 2=II, 3=III, 4=IV, 5=V, 6=VI, 7=VII, 8=VIII, 9=IX, 10=X, 20=XX, 30=XXX,, 40=XL, 56=LVI, 60=LX, 70=LXX, 80=LXXX, 90=XC, 156=CLVI, 272=CCLXXII, 300=CCC, 489=CDLXXXIX, 500=D, 634=DCXXXIV, 700=DCC, 800=DCCC, 900=CM, 1497= MCDXCVII. 1983=MCMLXXXIII, 이러한 예를 살펴보고 로마 숫자 표기 규칙을 이해하도록 한다.

4. 4=IIII로 표기할 수도 있지만 표기를 간단히 하기

위하여 IV로 표기한다. 이러한 표기는 4 뿐만 아니라 여러 경우가 있는데 예를 들어 9, 40, 90, 400 등은 각각 IX, XL, XC, CD 등으로 표기한다.

두 개의 로마 숫자가 주어졌을 때 이의 합을 출력하는 프로그램을 작성하시오. 입출력 형식은 다음과 같다.

입력: 입력의 첫 줄은 테스트 케이스의 개수 T가 주어진다(T  1,000). 각 테스트 케이스는 두 줄씩 1보다 크거나 같고 1000보다 작거나 같은 두 개의 로마 숫자가 주어진다.

출력: 각 테스트 케이스에 대해 덧셈 결과를 로마 숫자로 표기한다. 이의 10진수 덧셈 결과도 아울러 출력한다.

입출력 예: 입력 출력

2. CMLXXX+XIX=IM

CMLXXX980+19=999

XIXCLVI+XLIII=CIC

CLVI156+43=199

XLIII

문제 2. 영리한 생쥐

M  N 개의 격자 모양의 작은 방으로 구성된 구조물에 생쥐의 먹이가 놓여 있다. 구조물의 각 방에는 생쥐의 먹이가 1 개 이상 있거나 또는 없을 수 있다 (아래 그림 참조). 생쥐는 입구에서

들어와서 최대 개수의

먹이를 먹고 출구로 나가려고 한다. 그림에서 보인 바와 같이 각 방에는

외곽 벽을 제외하고 사방으로 통로가 있다. 그러나 생쥐는 일단 입구를 통하여 진입하면 최소의 방을 거쳐 출구로 나가야 한다. 그림의 경우 생쥐가

지날수있는방의수는 8이다.

생쥐가 최대 개수의 먹이를 먹고 출구로 나올 때까지 생쥐가 먹은 먹이 수를 계산하여 출력하는 프로그 램을 작성하시오. 프로그램의 입출력은 stdin과 stdout을 사용한다.

입력: 입력은 K 개의 테스트 케이스로 주어지며 K는 입력의 첫 줄에 주어진다. 각 테스트 케이스는 첫 줄에 테스트 케이스의 행의 수 M과 열의 수 N이 주어진다 (N, M  100). 이어지는 줄에는 각 행별로 먹이의 수가 N 개 씩 주어진다. 먹이의 수 사이에는 빈칸이 하나씩 있다. 먹이의 수는 100이하라고 가정한다.

출력: 각 테스트 케이스에 대하여 생쥐가 먹은 먹이의 수를 한 줄에 하나씩 출력한다.

주의: 입력에 적절한 시간 동안 수행시켜 결과가 출력되지 않으면 프로그램 작성에 실패한 것으로 간주합니다.