# '프로그래밍/알고리즘 문제'에 해당되는 글 3건

## 알고리즘 문제 - 알고스팟 Conversions 문제

프로그래밍/알고리즘 문제 2014.02.06 17:02

#### 문제

Conversion between the metric and English measurement systems is relatively simple. Often, it
involves either multiplying or dividing by a constant. You must write a program that converts between the following units:

Type Metric English equivalent
Weight 1.000 kilogram 2.2046 pounds
0.4536 kilograms 1.0000 pound
Volume 1.000 liter 0.2642 gallons
3.7854 liters 1.000 gallon

#### 입력

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.
Each dataset consists of a single line of input containing a floating point (double precision) number, a space and the unit specification for the measurement to be converted. The unit specification is one of kg, lb, l, or g referring to kilograms, pounds, liters and gallons respectively.

#### 출력

For each dataset, you should generate one line of output with the following values: The dataset
number as a decimal integer (start counting at one), a space, and the appropriately converted value rounded to 4 decimal places, a space and the unit specification for the converted value.

```5
1 kg
2 l
7 lb
3.5 g
0 l```

#### 예제 출력

```1 2.2046 lb
2 0.5284 g
3 3.1752 kg
4 13.2489 l
5 0.0000 g```
` `

답보기

#### '프로그래밍 > 알고리즘 문제' 카테고리의 다른 글

 알고리즘 문제 - 알고스팟 Conversions 문제  (0) 2014.02.06 2014.01.31 2014.01.30

## 알고리즘 문제 - 알고스팟 XHAENEUNG 문제

프로그래밍/알고리즘 문제 2014.01.31 16:41

#### 문제

산업 기능 요원 복무를 무사히 마치고 학교로 돌아온 xhae는 최근 복학을 위한 많은 지출로 인해 자금난에 허덕이고 있었다. 이러한 xhae가 선택한 일은 다름 아닌 째능 수학 영어 채점 아르바이트다. 복학 후 수업 참여와 ICPC 대회 준비로 인해 시간이 없던 xhae에게는 더할 나위 없는 자금 공급원이다.
째능 수학 영어는 초등학교 저학년 학생들을 대상으로 수학과 영어를 동시에 가르치려는 목적의 학습지며, xhae가 하는 일은 사칙연산 문제 학습지를 채점하는 일이다.
다른 유사 학습지와 다르게 째능 수학 영어는 사칙 연산 문제를 독특하게 낸다. 가령 "1 + 2 = "와 같은 문제의 경우 수를 영문으로 풀어 씀으로써 "one + two = "로 문제가 출제된다. 또한 답 역시 아라비아 숫자가 아닌 영문으로 풀어 쓴 수로 답을 적어야 한다. 즉, 위의 예시의 경우 "three" 라고 답을 작성하여야 한다.
처음으로 채점할 답지를 받아는 xhae는 오랜 ICPC의 경험으로 인해서인지 xhae는 채점을 할 때 답안에 오자가 있을 경우 가차 없이 이를 오답으로 채점했다. 예를 들어 "four"를 "fuor" 로 잘못 쓴 것을 오답으로 채점하였다. 하지만 채점 결과를 확인한 많은 학부형의 항의로 인해 xhae는 절충해서 다음과 같이 채점을 하려고 한다.
만약 답이 'seven'일 경우 적은 알파벳의 문자의 수가 동일하고(여기서는 's' 1개, 'e' 2개, 'v' 1개 그리고 'n' 1개), 순서가 뒤섞여 있는 경우까지는 정답으로 간주하기로 했다.
하지만 또 문제가 있다. 신중한 성격의 xhae라서 앞의 절충안을 생각을 하다 보니 채점을 해야 하는 답지가 너무 많이 쌓이게 된 것이다. 게다가 xhae가 학생들을 골탕먹이려고 0부터 10까지의 수밖에는 가르쳐주지 않은 채 답이 그 범위를 넘어설 수 있는 경우도 문제로 내는 바람에 채점이 더 골치아프게 되었다. 다행히도 xhae는 답지를 스캔하여 이를 텍스트로 완벽하게 변환 시킬 수 있는 세계 최고의 OCR장치를 가지고 있기 때문에 모든 답지를 텍스트로 변환해놓은 상태이며, 이를 자동으로 채점할 수 있는 프로그램을 짜려고 한다. 하지만 Coder's High 2013 에서 눈에 띠게 고생하고 있었던 xhae를 본 당신이라면 가볍게 이를 도와줄 수 있을 것이다.

고로, xhae를 도우기 위한 채점 프로그램을 작성하라.

#### 입력

입력의 첫 줄에는 채점을 해야 할 수식의 수 T가 입력된다. 각 수식은 한 줄에 입력되며 형식은 다음과 같다.

A operation B = C
.

여기서 A, B, C는 영문 단어로 나타낸 수를 뜻하며, operation은 더하기(+), 빼기(-), 곱하기(*)가 들어온다. A와 B를 구성하는 영문 단어는 0 이상 10 이하의 수를 나타내는 것으로써 순서대로 zero, one, two, three, four, five, six, seven, eight, nine, ten 중 하나가 항상 올바르게 주어진다. 반면 C의 경우 채점의 대상이므로 0부터 10까지의 수를 영문 단어로 표현한 것이 아닌 잘못된 문자열(예를 들어, 'hello')가 입력될 수 있다. 그럼에도 불구하고 이 문자열은 항상 길이가 10을 넘지 않는 알파벳 소문자로만 구성된 문자열임이 보장된다.

#### 출력

각 수식에 대해 입력된 순서대로 한 줄에 답이 올바르게 기재 되어 있으면 “Yes”를, 그렇지 않을 경우에는 “No”를 출력한다. 만약 연산의 결과가 0보다 작거나 10보다 클 경우에는 무조건 오답으로 간주한다.

#### 예제 입력

```2
two + three = ivef
zero * zero = one
```

#### 예제 출력

```Yes
No
```

이문제는 결국 못 풀었지만 답을 보니까 제가 문제를 잘못 접근했더군요.

답보기

#### '프로그래밍 > 알고리즘 문제' 카테고리의 다른 글

 알고리즘 문제 - 알고스팟 Conversions 문제  (0) 2014.02.06 2014.01.31 2014.01.30

## 알고리즘 문제 - 알고스팟 FESTIVAL 문제

프로그래밍/알고리즘 문제 2014.01.30 15:08
• 본 문제는 알고스팟(http://algospot.com/judge/problem/read/FESTIVAL)에 있는 문제입니다.
•

#### 문제

커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 밴드를 몇 팀 섭외할 지는 아직 결정하지 않았지만, 페스티벌의 간판 스타인 L개의 팀은 이미 섭외가 끝난 상태입니다. 따라서 페스티벌은 최소 L일 이상 진행하게 됩니다.

이번에 사용할 공연장은 하루 빌리는 데 드는 비용이 매일 매일 다릅니다. 때문에 공연 일정을 잘 정해서 공연장 대여 비용을 줄이려고 합니다. 앞으로 N일간의 공연장 대여 비용을 알고 있다고 합시다. 이 중 L일 이상을 연속해서 대여하되, 공연장을 하루 빌리는 데 드는 평균 비용을 최소화하려면 어떻게 공연장을 빌려야 할까요?

예를 들어 앞으로 6일간 공연장을 빌리는 데 드는 비용이 각 {3, 1, 2, 3, 1, 2}라고 합시다. 이미 세 팀을 섭외했다고 하면, 3일 대신 4일 동안 공연을 진행해서 평균 비용을 더 저렴하게 할 수 있습니다. 3일 동안의 평균 대여 비용을 최소화하는 방법은 2일째부터 4일째까지 공연장을 대여하는 것인데, 이 때 하루 평균 (1+2+3)/3 = 2의 비용이 듭니다. 반면 2일째부터 5일째까지 공연장을 대여하면 평균 비용이 (1+2+3+1)/4 = 7/4밖에 되지 않습니다.

#### 입력

입력의 첫 줄에는 테스트 케이스의 수 C (C ≤ 100)가 주어집니다. 각 테스트 케이스의 첫 줄에는 공연장을 대여할 수 있는 날들의 수 N (1 ≤ N ≤ 1000)과 이미 섭외한 공연 팀의 수 L (1 ≤ L ≤ 1000, L ≤ N)이 주어집니다. 그 다음 줄에는 N개의 숫자로 공연장 대여 비용이 날짜별로 주어집니다. 모든 비용은 100 이하의 자연수입니다.

#### 출력

입력에 주어지는 각 테스트 케이스마다 한 줄에 최소의 평균 대여 비용을 출력합니다. 10-7 이하의 절대/상대 오차가 있는 답은 정답 처리됩니다.

#### 예제 입력

```2
6 3
1 2 3 1 2 3
6 2
1 2 3 1 2 3```

#### 예제 출력

```1.75000000000
1.50000000000```
```저만의 풀이 방법을 소개해보겠습니다. 물론 저는 코딩 초보기때문에 속도도 느리고 효율도 떨어질것으로 봅니다. 저의 답은 수행시간 2985ms가 걸렸고 총 코드 비트수는 1.5kb입니다.

스포일 방지 더보기

day의 수 = 6 참가팀의 수 = 3 일 경우(1, 2, 3, 1, 2, 3) = 각 일별 코스트 모든 경우의 수를 써보면 3개씩 묶을 때 경우의 수 (1,2,3), (2,3,1), (3, 1, 2), (1, 2, 3) 4개씩 묶을 때 경우의 수(1, 2, 3, 1), (2, 3, 1, 2), (3, 1, 2, 3) 5개씩 묶을 때 경우의 수(1, 2, 3, 1, 2), (2, 3, 1, 2, 3) 6개씩 묶을 때 경우의 수(1, 2, 3, 1, 2, 3) 와 같다. 즉, 3개씩 묶을때는 4개의 경우가 있고 4개씩 묶을때는 3개 5개씩 묶을때는 2개 6개씩 묶을 때는 1개의 경우가 있으므로 4+3+2+1=7 총 7가지의 경우가 있음을 알 수 있다. 코드는 3개씩, 4개씩, 5개씩, 6개씩 묶을때 for문을 4번 돌리므로  days의 수 - 참가팀의 수 + 1 번을 돌리게 되는것과 같은 뜻이 된다. 그리고 3개씩 묶을때는 4개 이고 4개씩 묶을때는 3개 인것으로 보아 계속 1개씩 줄어드므로 days의 수 - 참가팀의 수 + blk_step으로 선언하고 blk_step은 처음에 1이었다가 각 한  경우의 수가 끝날때마다 blk_step을 1씩 줄여준다. 그리고 (1,2,3), (2,3,1), (3, 1, 2), (1, 2, 3) 으로 보면 배열의 인덱스로 보면 012, 123, 234, 345 처럼 start index가 1씩 늘어나므로 한번 끝날 때마다 start intext를 1씩 늘려주고 마지막 인덱스도 1씩 늘려줘야한다. 그리고 for문의 횟수는 x개씩 묶는것에 따라 다르므로 x번 돌려야한다. 이와같은 방법으로 모든 경우의 수를 파악하고 평균을 내서 가장 작은 값을 찾아서 출력하면된다. #include <iostream>//#include <string>//#include <iomanip>#include <stdio.h> using namespace std; int main(){         int testcase=0;        int min=0;        int days=0;        int nteam=0;        int dayCost={0,};        int sum=0;        double min_avg=9999.0;        double new_avg=9999.0;        double cout_avg={0.0,};         int step=0;        int start=0;        int blk_step=1;         //test case 받아줌        cin >> testcase;         for(int i=0; i < testcase; i++){                 //날짜수와팀갯수받아줌               scanf("%d", &days);               scanf("%d", &nteam);                 for(int j=0; j < days;j++){                        //날짜별비용받아줌.                       scanf("%d", &dayCost[j]);                }                step = nteam;//팀갯수로스탭시작               blk_step = 1;                              //전라인시작이니까               for(int n=0; n < days-nteam+1; n++){                         //한라인을돌릴때쓰는것이고                       for(int m=0; m < days-nteam+blk_step; m++){                               //더하는서브블록                              for(int k=start; k < start+step; k++){                                       sum = sum + dayCost[k];                                                                           }                               new_avg = (double)((double)sum/(double)step);//평균내보고                               if(new_avg < min_avg)//작으면갱신해줌                                      min_avg = new_avg;                               sum = 0;//sum 초기화해줌                               //start 세팅                              if(start <= days-step){                                                                            start++;                               }                                              }//한라인완료                               start = 0;//start 초기화                              blk_step=blk_step-1;//블록의전체횟수줄여주고                              step = step+1;//스탭늘려주고                 }//전라인완료.                cout_avg[i] = min_avg;               min_avg = 9999.9;//초기화          }         for(int i=0; i < testcase; i++){                printf("%.10f\n", cout_avg[i]);         }          return 0; }  다른분이 푸신 방법을 봤는데 첫번째에 (1, 2, 3) (1, 2, 3, 1) (1, 2, 3, 1, 2) (1, 2, 3, 1, 2, 3) 두번째에 (2, 3, 1,) (2, 3, 1, 2) (2, 3, 1, 2, 3) 세번째에 (3, 1, 2) (3, 1, 2, 3) 네번째에 (1, 2, 3) 으로 하면 훨씬 빠르고 간결하게 할수있었습니다..```

#### '프로그래밍 > 알고리즘 문제' 카테고리의 다른 글

 알고리즘 문제 - 알고스팟 Conversions 문제  (0) 2014.02.06 2014.01.31 2014.01.30