'strrev'에 해당되는 글 1건

  1. 2010.11.01 2010-10-23 모의테스트 해법

1. 문제에서 제시한 규칙을 천천히 따라하면 어렵지 않게 풀 수 있다.

 

2.

1) 주어진 내용을 그대로 따라서 작성할 수 있다.먼저 하나의 문자열로 입력받는다.‘+’를 만날 때까지 문자열을 str1 문자열에 복사한다.‘=’를 만날 때까지 문자열을 str2 문자열에 복사한다.나머지 문자열을 str3 문자열에 복사한다.각 문자열을 strrev(문자열) 함수를 이용하여 뒤집는다.이제 뒤집힌 각각의 문자열을 숫자 n1, n2, n3 로 변환한다.if ( n1 + n2 == n3) 인 경우에는 True 를 그렇지 않은 경우에는 False 를 출력한다.

2) 문자열을 입력받고 뒤집는 작업 없이 바로 숫자로 작성할 수 있다.문자열의 처음부터 숫자로 변환하는 것이다. 가중치를 적절히 조정하면 된다.문자열이 str 에 저장되어 있고 문자열의 길이가 len 이라고 할 경우int deci = 1;int n1 = 0;for(int i = 0 ; i < len ; i++){ n1 = n1 + deci * (str[i] - '0'); deci = deci * 10;}과 같은 형식을 이용하면 된다.



3. 찾는 숫자는 0 에서 9까지 수중 하나이므로 한 자리 수이다. 따라서 주어진 숫자가 무엇이든 상관없이 우리는 0에서 9까지의 숫자를 이용하여 test 해봄으로써 문제를 해결할 수 있다. 각각의 숫자를 배열에 나누어 넣어서 해결하는 긴 자리 덧셈을 이용한다.

- 자리수가 50자리까지 이므로 문자열로 입력받는다.- 입력받은 문자열을 숫자 배열에 하나씩 나누어 넣는다.- 0 더해 보고 원하는 숫자가 포함되어 있는지 알아본다. 있다면 종료한다.- 0에서 종료되지 않았다면 1을 더해본다. 있다면 종료한다. 없다면 원래의 값을 가지고 다음 단계로 넘어간다. 단, 1이상의 숫자를 테스트 할 경우에는 자리 올림 할 경우가 있으므로 주의한다.

 

 

4. 앞에서부터 생각하는 것이 힘들다면 거꾸로 생각해보자.

① 주머니가 한 개 남아 있다면 차례가 온 사람은 모두 가져가므로 승자가 된다. 따라서 Alice 의 차례라면 Alice는 구슬이 몇 개 들어 있든 모두 가져가야 이길 수 있다.

② 주머니가 두 개 있다고 가정해 보자.첫 째 주머니에 구슬이 한 개, 두 번째 주머니에 구슬 1개 이상 인 경우에는 Alice가 이길 방법이 없다. 첫 째 주머니 구슬을 Alice 가 가지고 가면 ①의 경우가 되어 Bob이 나머지 구슬을 모두 가지고 갈 것이기 때문이다.

③ 그런데 첫 째 주머니에 구슬이 2개 이상인 경우에는 Alice가 이길 수 있다. 첫 째 주머니에 구슬을 한 개만 남겨 놓으면 되기 때문이다. Bob이 두 번째 주머니에 남은 한 개의 구슬을 가져 갈 수밖에 없으므로 ①의 경우가 되어 차례가 된 Alice가 마지막 주머니의 구슬을 모두 가져간다.

④ 주머니가 세 개 이상이 되면 생각할 것이 많아진다. 하지만 마지막 주머니를 Alice이 가지고 간다고 가정하고 거꾸로 계산하여 첫 주머니까지 도달 했을 때 Alice가 첫 주머니의 구슬을 가지고 갈 수 있다면 Alice가 이기는 것이고 그렇지 못하다면 Bob이 이기는 것으로 답을 구할 수 있다.

예를 들어보자. 7번 주머니의 구슬을 Alice가 가지고 간다고 가정한다. 따라서 역으로 생각하여 7번 주머니에서 1번 주머니까지 진행한다.

주머니번호

1

2

3

4

5

6

7

구슬개수

1

2

3

1

1

1

3

Alice

 

1

2

1

 

5

3

Bob

1

1

1

 

1

1

 

설명

선택의
여지가
없다.
따라서
Bob 승

3번
주머니의
구슬을
Alice가
먼저
가지고
가야 한다.

4번
주머니가
Alice
차례가
되어야
한다.

선택의
여지가 없다.

7번
주머니가
Alice
차례가
되어야 한다.

Alice가
모두
가지고
가야
한다.


5. 이러한 문제의 경우

1) 문제의 제시 조건을 잘 파악하는 것이 중요하다.

2) 제시조건을 온전히 이해한 후에는 단순 반복문을 이용하여 시간제한이 허락하는 범위까지는 부분점수를 받을 수 있도록 하나의 프로그램을 작성해 놓는다.

3) 단순 반복문을 이용하여 여러 예들을 출력한 후에 규칙성을 찾아보려는 노력이 필요하다. 더구나 N 제한이 10억까지 이므로 단순히 N번을 반복한다면 시간 초과에 걸린다.

4) 단순 반복문을 이용한 출력 결과를 보면 재미있게도 토끼수들은 0, 1, 2, 3 만으로 구성되어 있다는 것을 알 수 있다.그 이유는 4이상의 수를 포함하게 되면 곱의 결과값이 곱에 못 미치기 때문이다.예를 들면 4 * 4 = 16 인데 결과 값 16의 각 자리 수를 더하면 7밖에 되지 않는다.5 * 5 = 25 인데 결과 값 25의 각 자리 수를 더하면 7밖에 되지 않는다.이후의 숫자는 더욱 차이가 벌어진다.

5) 따라서 우리는 배열을 큐로 이용하여 1, 2, 3으로 초기화 한 후에 이 수들을 10의 자리로 하여 만들어진 10, 11, 12, 13, 20, 21, 22, 23 ...의 수들이 토끼수가 되는지 확인하여 큐에 삽입한다. 이러한 식으로 10억까지 모든 수를 짧은 시간에 구할 수 있다.

6) 이렇게 구하여진 수들은 자연히 오름차순 정렬이 되어 있으므로 입력 받는 두수 사이의 개수를 구하는 일은 아주 쉬운 문제가 된다.

Posted by 파이군
,