태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.
블로그 이미지
Lonewolf dlbo

calendar

1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30          

Notice

2010.08.14 23:27 Solving process

뭐, 그냥
말로만 풀고있다고 하는 것보다야 직접 보여주는게 낫겠다 싶어서 -_-a



보다시피 3번째 케이스에서 제대로 된 답이 안나오고 있음//


경로 탐색 방식상
3번째 케이스처럼 양방향 길이 존재하는 경우에 대한 처리가 아직 잘 안되고있음 :(

'Solving process' 카테고리의 다른 글

UVa 341 진행상황  (0) 2010.08.14
[PKU 1989. The Cow Lineup] 문제해석  (2) 2009.12.25
PKU [2234]. Matches Game. [WA]  (10) 2009.06.03
이걸 어떻게 구현해야 할 지  (1) 2009.01.22
[PKU 1904. King's Quest] 문제해석  (12) 2009.01.21
PKU [1089]. Intervals. [TLE].  (2) 2009.01.19
posted by Milkskin

댓글을 달아 주세요

2009.12.25 02:52 Solving process

N(10만 이하의 자연수)마리의 소가 K(1만 이하의 자연수)가지의 품종을 가지고 있다

그 N마리 소들의 품종을 수열로 나열해놓자

그러면 이 소수열(cow수열)에서 부분수열(연속하지 않아도 됨)을 찾을 수 있다

이 때, 1~K의 수들로 이루어진 임의의 수열 중 소수열의 부분수열이 아닌 것들이 있을 것이다

그러한 수열들 중 길이가 제일 짧은 수열의 길이를 출력하시오

―가 이 문제의 내용입니다 =_=



문제의 입출력 예시를 보면

[입력: 편의상 수열을 가로로 나열했습니다]
14 5
1 5 3 2 5 1 3 4 4 2 5 1 2 3
[출력]
3

입니다


힌트에도 버젓이 나와있습니다만,
영어를 잘 모르는 탓에 처음 문제가 올라왔을 땐 제대로 읽지도 않았는데요 -_-; 오늘(24일)은 유독 눈에 들어오더라구요

위 수열에서 단항(원문과 비교하자면 single digit)으로 이루어진 수열은 [1], [2], [3], [4], [5]가 모두 존재합니다

그리고 이항(two digit)으로 이루어진 25개의 수열 [1,1], [1,2], [1,3], [1,4], [1,5], [2,1], …, [5,4], [5,5]들도 모두 위의 소수열에서 찾아낼 수 있습니다

그러면 출력값이 3인 만큼,
삼항으로 이루어진 수열 중에서는 소수열의 부분수열이 아닌 것들도 있겠구나 하시겠지요

힌트 끝부분을 보시면 [2,2,4]는 찾을 수 없다고 쓰여있습니다


----------------

간단한 예시를 하나 들어봅시다
7 3
1 2 3 2 1 3 2

이 경우에도 출력값은 3이 나옵니다, 가장 간단하게 생각해서 [1,1,1]을 찾을 수 없기 때문인데요


개인적으로는 이것을 matrix에 대응시켜서 풀었습니다

단항 수열의 경우 1×3 matrix를 이용하였고,
(소수열 안에 [1], [2], [3]이 존재할 경우 각각의 위치에 true 대입)


이항 수열의 경우 3×3 matrix, 삼항 수열의 경우 3×3×3 matrix(?)를 이용하였습니다


3항 수열의 경우 [1,1,1], [2,1,1], [3,1,1], [3,3,1], [3,3,3]을 찾을 수 없다


이 방법의 경우 최대 [N/K]+1 차원까지 계산해야하기 때문에
시각적으로 형상화할 수 있는 것은 3항 수열(3차원, 큐브형태)까지입니다
(붉은색 대괄호는 가우스기호(고등학교과정)입니다)

최대 [N/K]+1 차원이라는 말은
다시 말하자면 출력값의 최대값이 [N/K]+1 정도 된다는 말과 같습니다 (거의 정확합니다)


-------------

이렇게 풀었는데도 TLE가 나온 이유를 살펴보자면

N과 K가 적당히 크고, 품종의 분포가 고를 경우 가장 시간이 오래 걸립니다
입출력 예시의 경우가 그 한 예라고 볼 수 있습니다

N = 14, K = 5 이므로 최대 차수는 [14/5]+1 = 3 이고, 이것은 곧
최대 5^1 + 5^2 + 5^3 = 155 번의 탐색을 하고 나서야 답이 나오게 됩니다


그럼 이제, N과 K가 적당히 크고 품종의 분포가 고를 경우를 가정해봅시다
N = 30000, K = 50, 각 품종당 600마리씩 존재

이 경우 최소 50^1 + 50^2 + 50^3 + … + 50^600 + 1 = ??? 번의 탐색을 하고 나서야 답이 나오게 되므로 당연히 TLE입니다


아.. 이래서 TLE였구나 -_-;;

'Solving process' 카테고리의 다른 글

UVa 341 진행상황  (0) 2010.08.14
[PKU 1989. The Cow Lineup] 문제해석  (2) 2009.12.25
PKU [2234]. Matches Game. [WA]  (10) 2009.06.03
이걸 어떻게 구현해야 할 지  (1) 2009.01.22
[PKU 1904. King's Quest] 문제해석  (12) 2009.01.21
PKU [1089]. Intervals. [TLE].  (2) 2009.01.19
posted by Milkskin

댓글을 달아 주세요

  1. milk 2010.01.16 19:37  Addr Edit/Del Reply

    해석 잘보았습니다.^^
    이 문제 해결하셨나요? 다차원배열로 푸는문제가 아닙니다.
    14 5
    (15325134)(425123)
    괄호친것 안에는1~5의 숫자가 모두 들어있죠. 여기서는 3자리 부분수열을 만들 수 없겠죠.
    7 3
    (1 2 3) ( 2 1 3 ) 2
    이 경우도 괄호를 묶을 수 있는 경우가 두 개 뿐이라 3자리 부분수열을 못만들게 됩니다.
    입력되는 숫자들에서 차례대로 1~K까지의 숫자들이 모두 포함된 묶음의 갯수만 알아내면 되는것이죠.

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2010.01.17 02:48  Addr Edit/Del

      이미 TLE를 받았을 때부터 다차원배열 코드는 버린지 오랩니다 ㅠㅠㅋ

      제가 여태까지 했던 노가다에서 그렇게 묶는 것만 빼고 왠만한건 해본듯한데 =_=
      물도 안나오는데서 우물판 격이군요;

2009.06.03 22:12 Solving process


WA 입니다.

님 게임(Nim Game) 의 일종인 것 같습니다만, 이 문제는 가져올 수 있는 갯수의 제한이
최대 쌓여진 뭉치의 갯수더군요.

그래서 간단하게 '뭉치의 갯수가 짝수이면 첫번째 플레이어는 이길 수 없는 거고, 홀수라면 이기겠다.'
... 라고 생각했습니다만, WA 입니다.



...

Why???????

'Solving process' 카테고리의 다른 글

UVa 341 진행상황  (0) 2010.08.14
[PKU 1989. The Cow Lineup] 문제해석  (2) 2009.12.25
PKU [2234]. Matches Game. [WA]  (10) 2009.06.03
이걸 어떻게 구현해야 할 지  (1) 2009.01.22
[PKU 1904. King's Quest] 문제해석  (12) 2009.01.21
PKU [1089]. Intervals. [TLE].  (2) 2009.01.19
posted by 비회원

댓글을 달아 주세요

  1. 혹시 모르니 홀짝 뒤집어보진 않겠나 하는 1人

  2. 나도 일단 계산식은 저걸로 나왔는데(?) 저 게임이 재미있어지려면 절반 이상 못가져가게 하던지 해야 할텐데 그런건 없어보였어.. 혹시 내가 해석 제대로 잘못한건가? (-)

    • Favicon of http://dlbo.tistory.com BlogIcon Lonewolf dlbo 2009.06.04 14:00  Addr Edit/Del

      Short Coding 책에도 나와있고, 내 코드랑 알고리즘이 동일해. 원리는 안나와있고 -_-; 내 코드도 사실 뽀록성이 짙은터라(GDT보다가 XOR 그냥 시켜보다가 이것도 해볼까.... 하니까 되길래 -_-;;;;)

  3. 테슬라 2009.06.05 15:33  Addr Edit/Del Reply

    음 1 1 1 2 일때 처음 플레이어가 2에서 한개 가져가면 1 1 1 1이니까 두 첫 두 첫 해서 첫번째 플레이어가 이길수 있지 않을까?

    • Favicon of http://sparkoflight.tistory.com BlogIcon Sparking 2009.06.05 17:19  Addr Edit/Del

      맞는 말이긴 한데, 문제의 조건상 두 플레이어는 머리가 좋은걸? 자기가 질 방법을 스스로 택하는건 아닐거야..

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.06.05 20:08  Addr Edit/Del

      sparking//
      위와 같은 상황에서 처음사람이 2에서 한개 가져가면 나중사람은 머리가 좋든 나쁘든 빼도박도 못하고 짐 ㅋㅋ 선택권이 없음

    • Favicon of http://sparkoflight.tistory.com BlogIcon Sparking 2009.06.06 21:36  Addr Edit/Del

      Mr.K//
      그걸 모르는게 아니잖아.. 슬라군이 첫번째 플레이어가 홀수 개의 뭉치가 있을 때 질 수 있는 방법을 말하는데, 문제는 그 방법은 두 플레이어 모두가 똑똑하다라는 조건에 위배된다는 말을 쓰는거잖누. 그리고 처음 사람이 2에서 1개 가져가면 두번째 사람이 맨 마지막 성냥개비를 가져가니까 지는게 아니라 이기는거지..

  4. Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.06.07 23:33  Addr Edit/Del Reply

    sparking//
    홀수개의 뭉치라니?
    1 1 1 2 면 짝수개잖음?

    그리고 여기서 처음사람이 2에서 한개 가져가면 처음사람이 마지막 성냥개비도 가져감;

    • Favicon of http://sparkoflight.tistory.com BlogIcon Sparking 2009.06.09 01:25  Addr Edit/Del

      ㅇㅇ 지금 그걸 깨닫고 뒤늦게 탄식.
      난 병신이 맞나봐
      슬라군 미안 내가 잘못이해해놓고 사람 바보취급했구나 (..)

2009.01.22 17:47 Solving process
세 번째 케이스

6
3 1 2 3
3 2 4 6
2 3 4
1 5
2 3 6
4 1 2 4 5
//1 2 3 5 6 4



3 1 2 3
3 2 4 6
2 3 4
1 5
2 3 6
3 1 2 4

이 방법이 맞지요?

'Solving process' 카테고리의 다른 글

[PKU 1989. The Cow Lineup] 문제해석  (2) 2009.12.25
PKU [2234]. Matches Game. [WA]  (10) 2009.06.03
이걸 어떻게 구현해야 할 지  (1) 2009.01.22
[PKU 1904. King's Quest] 문제해석  (12) 2009.01.21
PKU [1089]. Intervals. [TLE].  (2) 2009.01.19
Rush : Dlbo군의 Matrix Solution  (8) 2008.12.28
posted by 지환태

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.01.22 19:30  Addr Edit/Del Reply

    아, 그림으로 깔끔하게 해주셨네요

    세번째 케이스의 풀이는 이게 맞습니다 :)

2009.01.21 03:53 Solving process

안녕하십니까 Mr. K입니다
다들 이번 문제에 대해 혼란스러워하는 것 같아서 일단 제가 해석한 대로 전개해보겠습니다

친구와 약간의 음주를 하고 와서 쓰는 것이라 약간 말이 안되어보이는 것이 있을지도 모르겠습니다만 그냥 쓰겠습니다


문제의 입력 예시를 보면
4
2 1 2
2 1 2
2 2 3
2 3 4
1 2 3 4
라고 되어있는데,
여기서 마지막줄의 "1 2 3 4", 즉 '마법사가 만들었던 원래의 결과물'은 무시하기로 합니다
(왜 우리가 output으로 나와야 하는 한가지 경우의 수를 input으로 넣어야 하는지에 대한 의문도 잠시 접어두기로 하고)


그리고나서
2 1 2
2 1 2
2 2 3
2 3 4
를 보면,
첫번째 왕자는 2명의 소녀를 좋아하고, 그 소녀의 번호는 각각 12입니다
두번째 왕자는 2명의 소녀를 좋아하고, 그 소녀의 번호는 각각 1과 2입니다
세번째 왕자는 2명의 소녀를 좋아하고, 그 소녀의 번호는 각각 2와 3입니다
네번째 왕자는 2명의 소녀를 좋아하고, 그 소녀의 번호는 각각 3과 4입니다

이것을 표로 그리면 아래와 같은데요


문제가 요구하는 것이 무엇인고 하니,

왕자(B)와 소녀(G)가 겹치지 않도록 일대일로 짝을 지어주는 모든 경우를 세고,
어느 왕자도 결혼하지 않은 상태를 가정하고 각 왕자가 다른 왕자의 결혼을 방해하지 않도록 선택할 수 있는 소녀를 모두 나열하는 것입니다

말이 좀 어려운데,
문제에 나온 예시를 먼저 보도록 하죠
위의 표를 참고해도 좋습니다

우선, 1번 왕자와 1번 소녀를 결혼시킵니다
그러면 2번 왕자는 1번 왕자와 같은 소녀를 고르면 안되므로 2번 소녀와 결혼시킵니다
그러면 3번 왕자는 1,2번 왕자와 같은 소녀를 고르면 안되므로 3번 소녀와 결혼시킵니다
마찬가지로 4번 왕자는 1~3번 왕자와 같은 소녀를 고르면 안되므로 4번 소녀와 결혼시킵니다

그러면 (1, 1) - (2, 2) - (3, 3) - (4, 4) 와 같은 한가지 경우가 만들어집니다

그런데 1번 왕자는 2번 소녀도 좋아하므로 위에서 했던 작업은 다 잊어버리고,
1번 왕자와 2번 소녀를 결혼시킵니다
2번 왕자는 1번 왕자와 같은 소녀를 고르면 안되므로 1번 소녀와 결혼시킵니다
그러면 3번 왕자는 1, 2번 왕자와 같은 소녀를 고르면 안되므로 3번 소녀와 결혼시킵니다
그리고 4번 왕자는 1~3번 왕자와 같은 소녀를 고르면 안되므로 4번 소녀와 결혼시킵니다

그러면 (1, 2) - (2, 1) - (3, 3) - (4, 4) 와 같은 한가지 경우가 만들어집니다

이 결과를 정리해보면,
어느 왕자도 결혼하지 않은 상태를 가정했을 때,
1번 왕자는 1번 소녀나 2번 소녀를 선택할 수 있습니다
2번 왕자도 1번 소녀나 2번 소녀를 선택할 수 있습니다
3번 왕자는 3번 소녀만을 선택할 수 있습니다
4번 왕자는 4번 소녀만을 선택할 수 있습니다

그래서 출력 예시에
2 1 2
2 1 2
1 3
1 4
가 나오는 것이 아닐까 생각해봅니다



이 문제를 풀면서 혼자 만들어본 케이스가 2개 더 있습니다
두번째 케이스입니다


이번에도 역시
1번 왕자를 1번 소녀와 결혼시킵니다
이 때, 2번 왕자는 2번 소녀와 3번 소녀 모두와 결혼할 수 있는데, 3번 소녀와 결혼시키게 되면 3번 왕자가 결혼할 수 없게 됩니다
그러므로 2번 왕자는 2번 소녀와 결혼시킵니다
그러면 3번 왕자는 3번 소녀와 결혼하게 됩니다

그리고나서 보면 4번 왕자는 3~5번 소녀를,
5번 왕자는 4, 5번 소녀를 좋아하고 있으므로 (4, 4) - (5, 5) 나 (4, 5) - (5, 4) 로 결혼시킬 수 있습니다
따라서 이 경우엔
(1, 1) - (2, 2) - (3, 3) - (4, 4) - (5, 5) 또는 (1, 1) - (2, 2) - (3, 3) - (4, 5) - (5, 4) 의 두가지 경우가 가능합니다

다음,
1번 왕자를 2번 소녀와 결혼시킵니다
그러면 2번 왕자는 3번 소녀와 결혼하게 됩니다
그러면 3번 왕자는 1번 소녀와 결혼하게 됩니다
4번 왕자와 5번 왕자는 위의 경우와 같은 꼴이므로 이 경우에는
(1, 2) - (2, 3) - (3, 1) - (4, 4) - (5, 5) 또는 (1, 2) - (2, 3) - (3, 1) - (4, 5) - (5, 4) 의 두가지 경우가 가능해집니다

따라서 이번 케이스에서는 총 네가지 경우가 가능한데,
역시 어느 왕자도 결혼하지 않은 상태를 가정하면
1번 왕자는 1번 소녀나 2번 소녀를 선택할 수 있습니다
2번 왕자는 2번 소녀나 3번 소녀를 선택할 수 있습니다
3번 왕자는 1번 소녀나 3번 소녀를 선택할 수 있습니다
4번 왕자는 4번 소녀나 5번 소녀를 선택할 수 있습니다
5번 왕자도 4번 소녀나 5번 소녀를 선택할 수 있습니다

따라서 이 케이스의 출력 예시는
2 1 2
2 2 3
2 1 3
2 4 5
2 4 5
가 아닐까 예상해봅니다



세번째 케이스입니다


이 케이스는 총 여섯가지 경우가 가능한데,
말로 풀어쓰면 길어지므로 직접 종이에 끄적여보세요 :)

(1, 1) - (2, 2) - (3, 3) - (4, 5) - (5, 6) - (6, 4)
(1, 1) - (2, 4) - (3, 3) - (4, 5) - (5, 6) - (6, 2)
(1, 1) - (2, 6) - (3, 4) - (4, 5) - (5, 3) - (6, 2)
(1, 2) - (2, 4) - (3, 3) - (4, 5) - (5, 6) - (6, 1)
(1, 2) - (2, 6) - (3, 4) - (4, 5) - (5, 3) - (6, 1)
(1, 3) - (2, 2) - (3, 4) - (4, 5) - (5, 6) - (6, 1)

그렇다면 이 케이스의 출력 예시는
3 1 2 3
3 2 4 6
2 3 4
1 5
2 3 6
3 1 2 4
가 되는 것이 아닐까 생각합니다


-만,

환타님의 WA 소스는 이 세번째 케이스의 답이 제 생각과 다릅니다 =_=

※ 처음에도 언급했지만, 이 풀이는 'sparking의 번역본'을 보고 나름대로 의미를 생각해서 풀었기 때문에 실제 답과 같다는 보장은 없습니다 :(
posted by Milkskin

댓글을 달아 주세요

  1. 그러나 나 역시 자네와 같은 생각이라네

  2. ... 그래도 이해 안감.

  3. "어느 왕자도 결혼하지 않은 상태를 가정하고 각 왕자가 다른 왕자의 결혼을 방해하지 않도록 선택할 수 있는 소녀를 모두 나열하는 것입니다" 문제가 말이 되려면 이렇게 되야 하는군. -_-;; 이 부분은 이해 감. 이걸로 DFS 뿐만 아니라 개념적 백트래킹 기법도 사용 가능하겠군.

  4. 그렇다고 봐야지. 모든 왕자는 전부 결혼해야 하니 다른 사람들에게 방해받아서 한 명이 좋아하는 여자를 다 뺏기면 그건 병신(응?)

    아니, 아무튼, ..뭐야. 내가 문제 번역을 가장 먼저 했다는건 인정하지만, 들보 너 아프다더니 뇌 활동이 좀 둔해진듯.. 그러게 몸 컨디션 관리좀 하지 그랬냐

  5. Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2009.01.22 16:23  Addr Edit/Del Reply

    세 번째 테스트 케이스 답이 내 계산하고 좀 다른데. -_-;

    3 1 2 3
    3 2 4 6
    2 3 4
    1 5
    2 3 6
    4 1 2 4 5

    아닌가?

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.01.22 19:31  Addr Edit/Del

      4번 왕자는 5번 소녀 하나만 좋아하는 상태이므로

      이 둘을 항상 연결해주려면 6번 왕자는 5번 소녀를 택하면 안되겠지;

    • Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2009.01.22 19:53  Addr Edit/Del

      계산 미스였군 -_-;;;

      환타님 그림보고 잘못했다는 걸 깨달았어 -_-;;;;;;;

  6. Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2009.01.22 16:36  Addr Edit/Del Reply

    그리고 Dlbo 군 말대로 DFS 를 통해 순회해 가는 것이 가장 정석적인 방법일 듯.

    MR. K 처럼 2차원 행렬에서의 DFS 를 이용한 방법을 코딩중인데... 이게 쉽지 않네 -_-;;;

    다른 방법이 있을까?

  7. Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2009.01.22 17:29  Addr Edit/Del Reply

    갑자기 든 생각인데...

    이거 N - Queens question 을 응용할 수는 없을까?

    십자 방향으로 서로 교차하지 않게끔 2차원 행렬의 index 값을 탐색해 나가면 가능할 것도 같은데.

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.01.24 00:57  Addr Edit/Del

      N-Queens랑 문제 푸는 방식이 같을 것 같긴 하네

      다만 Queen을 놓는 자리에 제한이 있을 뿐 -_-;

  8. 백트래킹을 이용한 방법은 어뗘? 재귀호출을 이용한 방법이면 생각보다 쉽긴 한데, TL 걸릴 지도 모르겠다 -ㅁ-;;

2009.01.19 16:56 Solving process


In PKU judge system.
사용자 삽입 이미지


허 -_- 간만에 시도해 봤는데... 감이 안돌아왔는지. 해답을 못 찾겠군요 -_-;;
꽤나 자신있게 풀었는데 말이죠. 쩝.

일단 closed_interval 이라는 구조체를 선언하고, 이 구조체를 배열에 저장합니다.
그리고 나서 각 closed interval 의 initial point, final point 를 기록합니다.
이 다음엔 Bubble Sort 로 각 구조체 배열을 정렬하죠.

그 뒤, 우선 제일 첫번째 index 의 initial point, final point 를 각각 case_min, case_max 변수에 저장하고, 각 구간값을 비교해
나갑니다.

next index 의 final 값이 case_max 값보다 크다면 이는 구간의 확장이라 보면 될 것이므로, case_max 값에
next index 의 final 값을 대입하고 다음 루프로 넘어갑니다.

만약 next index 의 initial 값이 case_max 값보다 크다면 interval 이 분할된 것이므로, 현 탐색위치의 initial point, final point를
출력하고, next index 의 탐색을 시작합니다.
탐색시, initial point 와 final point 의 초기화는 당연히 해야 겠죠.

그래서 루프를 나올 때는, 가장 마지막의 initial, final point 역시 출력해 줘야겠죠. -_-...

알고리즘상 문제는 없다고 보여집니다만, TLE 로군요. 다른 방법을 찾아야 하나...





*덧)
차라리 closed interval 을 대수적인 면에서 보기 보단 집합으로 취급하는것도 한 방법일 수 있겠네요.
각 closed interval 의 합집합을 구하면 될 것 같긴 합니다만.

생각 좀 더 해봐야겠네요 -_-;
posted by 비회원

댓글을 달아 주세요

  1. 버블소트가 문제여 ㅁ_ㅁ

  2. Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.01.21 02:46  Addr Edit/Del Reply

    dlbo군 말에 동감,
    아마 이런 류의 문제의 TLE는 sorting이 너무 오래걸려서 그런듯

2008.12.28 16:01 Solving process

네, 논란이 많았죠, Matrix


류엔트군은 술마시고 코딩해서 기억이 안난다고 하질 않나

Dlbo군은 류엔트군의 풀이와 99% 같은 코드를 올리고는
미리 풀긴 했는데 정리를 못한 상태에서 류엔트군의 AC가 올라오니까 그걸 보고 자기 풀이의 군더더기를 뺐다고 하질 않나
(사실 물증이 없어서 아직도 1%정도 의심은 가지만, 여기선 그걸 추궁하는게 아니니까 그냥 믿고 넘어갑니다)


그것 때문에 제가 뭔가 납득이 갈 만한 풀이를 올려달라고 했고,
얼마 전에 Dlbo군이 솔루션을 올려주었지요

솔루션을 읽고나서 알고리즘을 직접 적용해보니 아주 정확히 답이 떨어집니다

알고리즘의 목적( M번째 작은 값을 K라 가정하고, K보다 작은 값을 가지는 행렬상의 원소의 개수를 counting하는 것 )도 꽤나 깔끔하고, 합리적이지요

결론부터 먼저 말하자면,
저 코드로 아주 정확히 답을 찾아낼 수 있으니까
Dlbo군의 솔루션이 이해가 되는 분들은 과감히 '뒤로가기'를 눌러주셔도 됩니다



----------------------------------------

이제 Dlbo군의 솔루션이 뭔소린고 하는 분들만 이 아래를 보시면 됩니다

문제가 되는 부분은 Dlbo군의 설명부분인데..


일단,
솔루션에서의 x와 코드상의 x가 다른 의미를 가지고 있는 상태에서 표기가 중복되므로 의미의 모호함을 가질 수 있습니다
솔루션의 본문을 잘 읽으면 그것에 대해 언급을 했지만, 처음 솔루션을 보는 사람들에게는 난감할 수 있지요

어차피 AC받은거 또 제출할 일은 없으니 코드의 일부를 솔루션에 맞춰서 수정했어도 좋았을거라는 생각은 들지만.. 뭐 그건 상관없습니다


하나 더,
행에 관한 변수 i를 x로 치환해놓고,
j에 대해 언급할 때 '열'이 아닌 '줄'이라고 표현을 했는데, 이것 역시 처음 솔루션을 보는 사람들에게 매우 난감할 수 있습니다


그리고 자기 코드에 대해 잘 설명하다가 중간중간 류엔트의 코드와의 차이점을 언급하는데,
이건 읽는 사람의 몰입도에 방해를 줄 수 있으니 참고하세요 -_-;


또,
외부 while문이 min < max인 동안 돌도록 설계된 것이 류엔트군의 실수라고 했는데,
그러는 너는 왜 while문이 min < max인 동안 돌도록 해놨나여 ㅇㅇ?


그리고
cal_1( 이하 α; 알파라고 하겠습니다 )과 cal_2( 이하 β; 베타라고 하겠습니다 )가 실수값이 나오는 것에 대해 좀 걱정을 해놨던데
K가 무슨 값을 갖든지 알파와 베타가 정수값이 안나오는 열이 존재합니다

알고리즘을 돌리면서 확인해보니 알파와 베타는 실수값이 나와도 상관없습니다 -_-;

알고리즘을 몇번 돌려본 것을 바탕으로 추측해보건대, 알파는 항상 음수가 나옵니다
베타는 음수가 나올 때도 있고 양수가 나올 때도 있는데,
베타가 음수일 때는 고려하지 않으니 패스하고, 베타가 양수가 되면 알파·베타 모두 integer형에 쑤셔넣듯이 truncate하면 됩니다


그리고 예전에 Dlbo군이 코드에 쓰인 j는 사실 j가 아니고 i다 라는 말을 했었는데
솔루션을 읽어보니 그건 그냥 j가 맞습니다, 패스


아 마지막으로,
Dlbo군은 변수 det가 음수가 될 때의 경우는 전혀 생각하지 않은 듯 한데 -_-
우리의 자비로운 sqrt함수는 input으로 음수가 들어오니 output으로 0을 반환해주더군요

하지만 det에 대한 처리는 류엔트군의 코드가 맞으니 참고하세요 -_-;



----------------------------------------

이제 태클은 대충 됐고,

제가 예전에 Solving Process에 올렸던 1/5000 사이즈의 문제에 대해서 이 알고리즘을 적용해보겠습니다


i행 j열의 원소의 값을 나타내는 식 a_ij는 i² + 100000i + j² - 100000j + ij 인데,

행렬의 최대 사이즈가 될 수 있는 50000에 대해 다루기가 힘들기 때문에,
크기를 1/5000로 줄여서 최대 사이즈를 10으로 고정합니다

이때 a_ij를 보면
작은 수로 취급될 법한 i, j에 비해 큰 수 100000이 있는데,
최대 사이즈 50000을 10으로 줄였으니 위의 100000은 20으로 줄여보도록 합시다

그러면 우리는 a_ij = i² + 20i + j² - 20j + ij 를 얻을 수 있고,
N을 10( 최대 사이즈 )으로 고정하면 다음과 같은 행렬을 얻을 수 있습니다

위에서 붉은색으로 강조된 부분은 각 행에서 최소값을 가지는 원소를 표시해놓은 것입니다만,
파일을 재활용한 것이므로 이 풀이에서는 별로 필요 없습니다


이렇게 5만과 10만에 대해 각각 1/5000을 적용한 위의 행렬은
기존 문제( PKU 3685 )에서 제시하는 최대 5만×5만짜리 행렬이 갖는 성질을 그대로 가집니다

이제 M을 적당히 하나 잡아서, M번째 작은 값을 솔루션의 알고리즘을 통해 위의 행렬에서 찾아보도록 합시다



( 엑셀 2007에서 작성한 문서입니다 )


사용자가 수동으로 바꿔줘야하는 값은 max, min, M 세가지 뿐이니

max의 초기값은 400으로, min의 초기값은 -400으로, M은 1 이상 100 이하로 적당히 잡고

소스의 아랫부분에 있는 if( sum < M ) … else … 부분의 statement에 대해서만 수동으로 바꿔주면 됩니다

그러다보면 언젠가 max와 min이 같아지는 때가 나오는데,

그 때가 되면 더이상 while문을 돌지 않으므로 그게 답이 됩니다

- End -
posted by Milkskin

댓글을 달아 주세요

  1. "외부 while문이 min < max인 동안 돌도록 설계된 것이 류엔트군의 실수라고 했는데," -> 이미 말했듯, 그때 나도 정신없던 때라 완전히 코드에서 군더더기를 없앤 상태는 아니었음.

  2. "Dlbo군은 변수 det가 음수가 될 때의 경우는 전혀 생각하지 않은 듯 한데 -_-" sqrt도 함수이기 때문에 실패했을 경우는 false에 해당하는 0을 리턴. 이부분은 따로 언급이 필요 없었음.

  3. "행에 관한 변수 i를 x로 치환해놓고,
    j에 대해 언급할 때 '열'이 아닌 '줄'이라고 표현을 했는데, 이것 역시 처음 솔루션을 보는 사람들에게 매우 난감할 수 있습니다"와 "솔루션에서의 x와 코드상의 x가 다른 의미를 가지고 있는 상태에서 표기가 중복되므로 의미의 모호함을 가질 수 있습니다
    솔루션의 본문을 잘 읽으면 그것에 대해 언급을 했지만, 처음 솔루션을 보는 사람들에게는 난감할 수 있지요"
    -> 포스트에 언급했음. 좌표평면의 축을 자유자재로 다루는 경우를 모르는 사람을 위해 변형해 설명.

  4. "알고리즘을 돌리면서 확인해보니 알파와 베타는 실수값이 나와도 상관없습니다 -_-;" -> 난 이부분이 왜 이런지 이해 아직 안됨.. -_-; 증명해주삼

  5. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.12.29 12:41  Addr Edit/Del Reply

    첫번째 리플// 그럼 while문이 min < max인 동안 도는게 군더더기란 말임 -_-? 난 딱 맞는 것 같은데

    두번째 리플// 그건 한줄정도 언급해야할만한 얘기였음

    세번째 리플// x에 대한 얘기 말고, 열을 줄로 바꿔말한것도 같은 이유임?

    네번째 리플// 집합론에서 증명 대신 벤-다이어그램을 제시하는 것 같아 좀 꺼림칙하지만, 첨부파일로 올린 엑셀 돌려보면 베타가 실수값이 나오는데도 불구하고 sum과 M의 비교에 따라 max나 min을 수정하는 작업이 트러블 없이 잘 됨

    • Favicon of http://dlbo.tistory.com BlogIcon Lonewolf dlbo 2008.12.29 22:54  Addr Edit/Del

      첫번째 - min과 max가 같아지는 순간까지만 돌아도 된단 얘기.
      두번쨰 - .... 글쎄 -_-;
      세번째 - ㅇㅇ
      네번째 - 왜 그런지 모르겠다니깐 -_-;

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.12.30 02:19  Addr Edit/Del

      첫번째// min과 max가 같아지는 순간까지 돌아도 된다는게 min < max일 때 while문을 돈다는 얘기 아님? -_-?

  6. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.12.29 12:43  Addr Edit/Del Reply

    이거 왜 발행했냐 -_-

2008.10.08 21:29 Solving process
http://ko.wikipedia.org/wiki/%EB%B0%80%EB%9F%AC-%EB%9D%BC%EB%B9%88_%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95

밀러-라빈 소수판정법에 관한 위키페디아의 링크입니다.

참 난감...한 소수판정법이긴 합니다.

"이건 일단 합성수다!"라고 판정은 할 수 있지만,

"이거 소수인거 같긴 한데..."라니 원 ㄱ-;;

우리가 풀었던 factovisor에서도 순수하게 그냥 소수로 쌩 때리면 풀기 힘든만큼,

테스트케이스에서 약간의 여유를 부려 밀러-라빈 소수판정법으로 풀 수 있게 해둔것 같습니다.

리턴군, 환타님, 저 세명의 코드에 대한 테스트케이스들의 결과로 보컨데 예상되는 형태의 테스트케이스들은

모두 밀러-라빈 소수판정법에 의해 걸러질 수 있는 형태입니다. -_-;
posted by Lonewolf dlbo

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.10.08 23:31  Addr Edit/Del Reply

    이런 판정이라면 그럴 수 있을지도;


    합동 연산이 있어서 보기 좀 귀찮다는게 좀.. -_-;

  2. 저는 예쁘게 다시 소인수분해로 풀어서 AC를 받았지요 ㅋㅋㅋ
    특정케이스가 중요한 게 실감나는문제였어요 ㅎㅎ

  3. Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2008.10.09 12:53  Addr Edit/Del Reply

    =_= 역시 수학은 재밌어(?)

2008.09.19 18:43 Solving process

Reuent님의 소스로 행X행의 행렬에서 열(A,B,C...AX)번째 원소를 정리해봤습니다.

규칙이 보이시나요?
 
전 안보여요 ㅜㅜㅜㅜㅜㅜㅜ
posted by 지환태

댓글을 달아 주세요

  1. Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2008.09.19 20:18  Addr Edit/Del Reply

    키얅 -_-;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

    설마 순수 노가다 뛰신 건가요?

    • Favicon of http://zfanta.com BlogIcon  환타 2008.09.20 00:18  Addr Edit/Del

      순수 노가다는 아니구요 ㅎㅎ 엑셀에 좋은 기능이 있더라구요~~ ㅎㅎ

  2. 규칙성 하나 찾았습니다. 1번째는 1 by 1 행렬. 3만 있지요. 2번째는 2 by 2 행렬. 3이 2번째 값이 됩니다.
    3번째는 3 by 3 행렬. 3이 4번째 원소입니다. 4번째는 4 by 4 행렬. 3이 8번째 원소입니다.
    몇 번째 원소이느냐가 3을 기준으로 본다면, n번째 n by n 행렬에서 어떤 두 원소의 위치는 n+1 by n+1에서두 원소 사이에 1개의 값이 추가됩니다.

  3. n by n에서 가장 작았던 원소는 n+1 by n+1에서는 2번째로, n by n에서 2번째로 작았던 원소는 n+1 by n+1에서는 4번째로 작은 원소가 되는 거네요.

  4. 아래로 내려갈수록 가장 작은 원소와 2번째로 작은 원소의 차이는 2씩 감소합니다. 2번째 2 by 2에서 99996부터 2씩 내려가는군요.

  5. 2번째와 3번째 원소 차는 2번째줄 3과 12의 차인 9부터 해서 3씩 증가합니다.

  6. 이거 아무래도 계차수열인듯?;;

    • Favicon of http://zfanta.com BlogIcon  환타 2008.09.20 00:20  Addr Edit/Del

      zzz
      계차수열 ㅇㅅㅇ 수학선생님께 한번 물어보고싶네요 ㅋㅋ
      어느 과정에서 나오나요???????

    • Favicon of http://dlbo.tistory.com BlogIcon Lonewolf dlbo 2008.09.20 01:01  Addr Edit/Del

      대략 고등학교 수1과정일겁니다. 군수열 혹은 계차수열인데... 두개를 섞어놓았을 지도;;; 수학과인 우리 Mr.K께서 강림하시면 어떤건지 알려줄지도 모릅니다 -_-;

  7. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.22 00:49  Addr Edit/Del Reply

    이거 읽어보니 규칙이 있긴 있는데

    1/5000로 줄여서 생각해봤을 때, 이 규칙은
    원래 문제에서는 행렬의 차수 N이 약 16667이하일 때만 성립하지 않을까 싶군요;


    엑셀파일에서 나타나는 규칙 자체는 다소 설명하기 까다롭지만

    결론만 놓고 말하자면,
    이 규칙이 성립하는 크기의 행렬에 대해서는

    우리가 여태까지 일반적으로 해왔던 ↘이 방향으로 오른쪽 위에서부터 읽어내려오는 방식이 유효하다는겁니다;

    이것에 대한 설명은 dizies님이 solving process에 올린 글이 있으니 참고하셔도 좋을듯;

2008.09.19 14:09 Solving process
우리가 문제에서 생각해야 하는 행렬의 최대 차수는 무려 5만차입니다
(여기서 말하는 차수는 행렬의 size를 의미합니다)

그리고 행렬 내의 i번째 행, j번째 열의 원소인 a_ij의 값은 i^2 + 100000*i + j^2 - 100000*j + i*j 이지요
(이하 a_ij는 (i, j)로 표기하겠습니다)

약간 고쳐서 간단히 만들면 (i+j)^2 - i*j + 100000*(i-j)가 됩니다


그런데 여태까지 ↘이 방향으로 오른쪽 위에서부터 왼쪽 아래까지 읽어내려오는 방식은
(즉, n차 행렬에 대해 (1, n), (1, n-1), (2, n), (1, n-2), (2, n-1), (3, n), (1, n-3), …, 이 순서로 읽어내려오는 )

행렬의 차원이 커지면 저 순서로 읽을 수 없게 되고 말아버립니다


그런데 최대 차수가 5만이니 차수를 하나하나 증가시키면서 검사하는 방법은 거의 불가능에 가깝다고 봅니다

그래서, 1/5000로 줄여서 최대 차수가 10차인 문제에 대해 생각해보도록 하겠습니다
단, 1/5000로 줄일 때
(i, j)의 값을 나타내는 식의 일부에 해당하는 '10만'에도 적용시켜서 (i, j) = (i+j)^2 - i*j + 20*(i-j)로 생각하도록 합니다

이렇게 계산해서 나타낸 10차 행렬은 다음과 같습니다



원소가 100개밖에 되지 않으니 다루기 훨씬 쉬워지긴 했지만

'원래 문제에서 발생하는 현상이 그대로' 위의 그림에도 존재합니다

이 행렬의 경우
'3차까지는' ↘이 방향으로 읽어내려오는 방식이 유효하지만 4차부터는 그렇지 않죠

게다가 차수가 더 커지면 각각의 행 안에서의 최소값이 오른쪽 끝에 있지 않습니다

붉은색으로 표시해둔 값이 각각 i번째 행 안에서의 최소값이 되는데, 이 최소값의 좌우로는 값이 커집니다



만약 이 행렬에 대해서 m번째로 작은 값을 '규칙적으로' 찾아낼 수 있다면

그것을 확장해서 원래 문제에 적용할 수 있지 않나 생각합니다만- 어떻게 생각하시는지?
posted by Milkskin

댓글을 달아 주세요

  1. Favicon of http://dizies.tistory.com BlogIcon dizies 2008.09.19 17:12  Addr Edit/Del Reply

    헉..

2008.09.19 02:04 Solving process
입력에 50000 1이랑 50000 2 넣어보세요.

기존 방식처럼 오른쪽 위에서부터 대각선 오른쪽 아래로 내려가는걸 반복하는 방식으로 풀었다면

두 입력에 대한 값이 같습니다.

ㅡ.,ㅡ...

아래는 i를 1부터 5까지, j는 49996부터 5만까지 연산한 결과값입니다.

-2499849987  -2499849993  -2499849997  (-2499849999  -2499849999)
-2499699988  -2499699993  -2499699996  -2499699997  -2499699996
-2499549987  -2499549991  -2499549993  -2499549993  -2499549991
-2499399984  -2499399987  -2499399988  -2499399987  -2499399984
-2499249979  -2499249981  -2499249981  -2499249979  -2499249975

괄호친부분 보세요.

같죠?-_-;

영 뭔가 이상하다 싶어서 구글링을 통해 AC받은 사람들의 평을 들었는데...

문제가 변태스럽다고, 수준이 심각하다고 하는 의견들을 입수했습니다.

학교서 수업도 안듣고 저거 계산하고 있었는데...

최초에 저 두부분 계산하려다가 그냥 말았거든요.

"설마 같겠냐"

-_-....;;

역시 설마가 사람잡는군요. 저걸 10만짜리 다음으로 시도할라 했었는데(10만짜리도 그냥 포기)

역시 정답률 18%는 그냥 18%가 아니군요.

저랑 같이 이시간에 수고한 Mr.K군에게 감사의 말 전합니다 -_-!

Reuent군은 정답률 최소 30%는 넘는걸로 앞으로 번역하도록 합시다 -_-;;



P.S.

이번 토요일 2시~ 5시에 algospot.com에서 ICPC 2008 Korea National 대비 모의고사가 있습니다.
참가할 분 있으면 지금 후딱 신청하시구요...
다들 메신져 쓰신다면 어느 메신저인지 달아주세요. 아이디는 일단 달지 마시구요. 비공개로 때리면 서로
못볼지도 모르니;;; 제가 한분 한분 찾아다 추가하겠습니다.
posted by Lonewolf dlbo

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.19 02:21  Addr Edit/Del Reply

    아니 그 방법으로 안풀어도 두 값이 같게 나와 계산해보면 -_-

    두 수의 값이 같은게 문제가 아니라니까;


    오른쪽 위에서부터 이(↘) 방향으로 읽어내려가면 order가 꼬인다는게 문제란 말이야 -_-;

    게다가 꽤 불규칙해보인다는 것도;

  2. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.19 16:05  Addr Edit/Del Reply

    근데 웃긴건

    정답률 16%짜리 트리섬은 푼 사람이 있는데 18%짜리 매트릭스는 아직 솔루션이 안올라왔다는거;

  3. 이 문제 단체전으로 가야 할 듯?????????
    너무 잔인하네요 ㄷㄷ

    • Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2008.09.19 19:30  Addr Edit/Del

      잔인해서 미안해요 ㄱ-

      앞으론 선정 잘 할게요 ㅠ_ㅠ

2008.09.18 20:20 Solving process

아직 AC 받은건 아닌듸요...

너무 피로해서 지금 죽을꺼 같아서 솔루션 만들어놓고도 코드로 못옮기고 있는데...

이거 확인해 보셨나요?

식이 i^2 + 100000i + j^2 - 100000j + ij 잖습니까...

i만 1 증가시켜 비교해 보면...

i^2 + 100000i + j^2 - 100000j +ij와 i^2 + 100000i + j^2 - 100000j +ij + 2i + j + 100001이 되어서

i 증가시 2i + j + 100001만큼 증가함을 알 수 있지요.

j만 증가시켜도 그렇겠지요?

(1,1)의 값이 3이니 굳이 저 연산 안하고 증감에 따른 차이만큼만 더해도 나와요.

-_-;
posted by Lonewolf dlbo

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.18 20:58  Addr Edit/Del Reply

    이거 확인해봤음?

    a_ij = i^2 + 100000i + j^2 - 100000j + ij 잖아

    i랑 j를 각각 c, d만큼 증가시켜보면

    a_(i+c)(j+d)
    = (i+c)^2 + 100000(i+c) + (j+d)^2 - 100000(j+d) + (i+c)(j+d)
    = i^2 + 2ic + c^2 + 100000i + 100000c + j^2 + 2jd + d^2 -100000j - 100000d + ij + id + jc + cd 이므로

    각각 c와 d만큼 증가했을 시 오차는 2ic + c^2 + 100000c + 2jd + d^2 - 100000d + id + jc + cd 가 되네


    근데 오차를 자세히 보면 c와 d에 대해 각각 2차식이잖은가?

    그래서 증감에 따른 차이가 일정하다고 보장받을 수 없음 -_-;

  2. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.18 21:11  Addr Edit/Del Reply

    ㅇㅇ 잠좀 자게

    나도 어제 이거 풀다가 3시에 잤더니 오늘 죽겠던디;

2008.09.17 16:30 Solving process

그냥 배열에 i*(i+100000)+j*(j-100000)+i*j 넣고 찾으면 되는건가요?

posted by 지환태
TAG 행렬

댓글을 달아 주세요

  1. 예 ㅁ_ㅁ; 2차원 배열을 행렬이라 부릅니다.

  2. 아참. 그리고 저거 그대로 다 계산했다가 하면 TL걸릴지도 몰라요 ㄱ-;

  3. Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2008.09.17 18:51  Addr Edit/Del Reply

    그냥 저대로 했다가는 배열 인덱스 오버플로우 떠서 -_-;; 아마도 RE 걸릴 것 같군요.
    - 최대 50,000 by 50,000 행렬을 검사합니다. TL 가능성도 농후하죠. -

    단순 해법보단 수학적 사고력이 필요할 듯 싶습니다. -_- 저도 WA 걸려서 다시 푸는 중이구요.

  4. 배열 인덱스 뿐만 아니라 연산중에도 오버플로 뜬다 ㄱ-

2008.09.14 16:16 Solving process

안친하던 재귀함수랑 좀 친해져보려고 재귀로 짜보긴 하는데요.........
어떤 처리를 더 해줘야 중간에서 안끝날까요?

하아...........


재귀랑은 안친해질 팔자인가
posted by 지환태

댓글을 달아 주세요

  1. 으흠... 문제점 첫 번째. 뭐... 엉뚱한 애기일지도 모르겠지만, 입력 형식중 숫자 직후 빈칸 없이 바로 '('가 시작되는 경우가 있습니다. 이 경우 메인함수의 tmp에 getchar를 시켜버린다면 문제가 발생하지요.

  2. 그리고 두번째. 왼쪽 노드만 검사하는 이유에 관련된 건데요. 입력시 트리 레벨이 원점이 될 때 까지 받아야 하지요? 그런데 판타님의 코드에서는 ')'를 만나면 리턴해버리게 되어 있습니다. 이 경우 (1()()) 를 입력한다면 (1()까지만 보고 바로 리턴되어버립니다. 왼쪽 노드밖에 검사가 안되는 이유이지요.

  3. 그리고 세번째 문제점. scanf는 숫자만 받긴 하지만.... scanf("%d", &i);일때 숫자가 아닌 '('나 ')'를 만난다면 i에 1을 입력시킨 후 scanf는 0을 리턴합니다. 간단히 말해 (1()())라면 최종 리프노드를 2로 계산하게 됩니다. 정확한 답이 나오지 않겠지요?

  4. 아마 리턴대신 continue를 쓰시는게 낫지 않을까 싶습니다.

  5. return 1을 쓰신 이유가 leaf를 증가시키기 위한 것이었군요. leaf++; continue;로 대체하셔도 무리없이 돌아갈 것 같습니다. 지금 다시 자세히 보니 판타님 코드가 가장 최적화된 모형인걸요? UVa에서 랭크 20위 내에 충분히 진입 가능할것 같아요~ 완성된다면 한번 꼭 넣어보세요 ㅁ_ㅁ!

2008.09.04 10:56 Solving process
22 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
20 (5(4(11(7()())(2()()))()) (8(13()())(4()(1()()))))
10 (3
     (2 (4 () () )
        (8 () () ) )
     (1 (6 () () )
        (4 () () ) ) )
5 ()

0 ()
-1 (-1()())
77 (77(1()())())
-77 (-77()())

-7 (1 (-6 (2 (1 ()()) (-4 ()(1 (1 ()())(-1 ()())
   ) ) )
      () ) () )

0 ()

3 (3 (4 (5 ()()) (8 (-3 (-7 ()())())(-4 ()(-8 ()()))))
(6 (6 (-5 ()())(-6 ()(-9 ()())))(7 ()())))

0 (1()
        (-2 () (1()())))

1 (1 () (0 ()()) )

0 (0 ()())

8(8(2(1()())())())
8(8(3(7()())())())
4(4(2(4()())())())
5(5(4()(1(7(3()())(4()()))(4(3()())())))())
21(7()(5()(5()(4(1(7()())())()))))
47(7(9()(1(4()(7()(5(9(3(4(10()())())())(5(9(5(6(3(1(9()(2(3()(9(1(3(7()())(9()()))(9(5()(2()()))()))(7()())))(5(2()(6()(2()())))())))())(7()(2()(3()()))))(9()(10(4()(3()(4(3()(5()()))())))())))(3()()))())()))(6(10()())()))))()))())
24(9()(6()(1(2(9(8(7()())(1(1(7()())())(8()())))())(6(5(9()())())()))())))
15(8()(3(7(4(4()(9(6(3(3()())(9(3(3(8()())(7()()))())()))(3()()))()))())())(3(1(8(5(4(2()(4()(3(1()(10()(9()())))())))())(2()()))())())())))
18(4(9()())(1()(4()(9(3(9()(7()(8(6()())(5()(5()())))))(8(4()(1()()))()))()))))
38

(5
  (6
    (4
      ()()
    )
    (3
      ()()
    )
  )
  (7
    (2
      (1
        ()()
      )
      (10
         ()
         (9
           (5
             ()()
           )
           (2
             ()()
           )
         )
      )
    )
    ()
  )
)
77 (77(1()())())
77 (77(1()())())
77 (77  (1 () ())  (0 () ()) )
77 (77 () ())
3
(1
  (1 (1 ()()) ())
  (2 ()       ())
)

3
(1
  (1 (2 ()()) ())
  (2 ()       ())
)


yes
no
yes
no
no
yes
no
yes
yes
no
yes
yes
yes
yes
no
no
no
no
no
no
no
no
no
yes
no
no
yes
yes
yes
yes


입력/출력 샘플입니다. -_-;
posted by Lonewolf dlbo

댓글을 달아 주세요

  1. 위 예시를 보시면 알겠지만 춉내 긴것도 있습니다. 문자열로 처리해선 안된다는걸 보여주지요 -_-;

  2. Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2008.09.05 00:54  Addr Edit/Del Reply

    카테고리 Solving process로 이동시켰심. ㅇ_ㅇ

  3. uva에 입력 출력샘플도 보여주나요?
    허억
    내가 까막눈이라 못찾는건가?

    • Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2008.09.06 00:36  Addr Edit/Del

      -_-a 따로 제공하진 않습니다만...

      사용자들의 문제풀이 커뮤니티에서 얻어낼 수 있죠.

  4. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.08 16:33  Addr Edit/Del Reply

    샘플중에 아래에서 5번째랑 6번째가 두줄 다

    77 (77(1()())())
    no

    로 되어있는데 한줄 빼도 되는거 아닌가?;

2008.09.04 01:24 Solving process


Mr.K의 솔루션입니다.

위 부분에서 첫번째 문제...

문제에는 "EOF까지 입력받아라~"라고 되어있습니다.

근데 이 처리가 없지요 -_-a;;

이 처리는 생각보다 단순합니다.



위와 같습니다.

scanf는 EOF를 만나면 데이터를 변수에 넣지 않고, EOF를 리턴합지요.

이 외의 경우 scanf는 읽어들이는데 성공한 변수의 갯수를 리턴합니다.

while문의 조건에 scanf가 EOF를 만나느냐 아니느냐를 가지고 처리하게 해 버리고

내부 처리 루틴을 이 안에 쑤셔넣음으로써 해결되지요.

UVa나 PKU에서 EOF를 만날때까지 입력받을때 항상 쓰이는 방법입니다.

일반적으로 UVa나 PKU는 입력이 남았는데도 프로그램이 종료될 경우

TLE(Time Limit Exceed)나 WA(Wrong Answer)중 자기 마음대로 나오는 경향이 있습니다.

UVa의 경우는 WA만 나오더군요.

-_-;

이후 45~ 53줄.

gets를 이용해 입력을 받고 있습니다.

이 경우 문제점이.....

자. 아래 입력 예시를 보세요.

3 (3()
())
4 (2(2()())
())

.....

첫 문장만 처리해야 하는데...

4 (2(2()()) 까지 gets가 먹어버립니다.

-_-;

로직상 문제 없지 않냐구요?

.....

문제 있어요 -_-;;

gets는 버퍼에 글을 쓴 후, 버퍼 내용을 지우지 않고 변수에 데이터를 넣고 끝냅니다.

고로.... 입력 버퍼와 변수에 저장할 버퍼 사이에서 gets 한번 더 호출시

'\0'의 위치가 엉킨다거나, 하는 문제가 발생합니다.

-_-;

한두번의 입력은 버텨내겠지만, 이후에는 RE(Runtime Error)나 WA(Wrong Answer)를

유도할 수 있습니다.

이 떄문에 제가 getchar로 하나하나 받아다 처리했다지요 -_-;;

제 경우는 scanf의 특성을 활용했습니다.

EOF를 만날 경우 EOF나 -1을 리턴하는것 외에도,

scanf("%d", &a);시 입력받은 부분이 숫자로 시작하지 않는다면 scanf는 1개중 1개를 읽는데 실패했으니

1 - 1 = 0, 즉, 0을 리턴합니다.

이리하여 제 경우는 처음 비교대상은 scanf로 받고, 이후 getchar로 (를 받을떄까지 달린 후, 바로 scanf

를 이용해 빈 노드인지 아닌지를 판별하고 넘어가는 방식을 썼습니다.

빈 노드가 아니라면 scanf가 1을 리턴함으로써 참이 될 테고, 이 경우 내부 노드를 추가 확인하는 작업,

빈 노드라면 scanf가 0을 리턴함으로써 거짓이 되니, 다시 한번 (를 찾아 getchar의 여행을 떠나는거지요.

-_-;;

이후 곽군 코드의 문제점.

스택에다가 아예 우르르 쌓아버린후 연산하는데...

TL 걸리기 딱 좋답니다.

WA 풀린다면 아마 TL이 또 한번 가로막을꺼에요.

-_-!;;;;

용호군은 현재 솔루션이 있으나, 다시 생각해 풀어 올린다 합니다.

용호군의 솔루션도 저와 비슷한데.... 전북대 ALPS의 솔루션과 매우 흡사합니다.

용호군이나 저나 getchar를 이용해 한글자씩 받으며 입력받음과 동시에 연산을 했습니다.

이리하여 만약 yes가 된다면, 이후에는 종료될때까지 입력만 받도록 처리되었지요.

특히 Mr.K의 솔루션에서는 구조체를 이용해 처리를 했는데,

구조체의 배열 크기를 300으로 잡았답지요.

gets를 썼다는 부분과 문자열로 처리했다는 부분, 노드 갯수를 300이라는 적은 숫자로 잡은 부분에서

큰 문제가 발생합니다.

문자열로 처리함으로써 만약 한 줄에 256자가 넘게 입력되거나, 한 입력문이 256자가 넘으면

바로 RE입죠.

-_-;

동시에, 노드 갯수(Mr.K는 카드)가 300개를 넘는 경우에도 RE가 발생합니다.

물론 저런 극악의 경우는 드물겠지만 말입니다. -_-;

이 부분에 대한 처리를 하고 나면 코드가 상당히 짧아짐과 동시에 안정성을 가질겁니다.
posted by Lonewolf dlbo

댓글을 달아 주세요

  1. Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2008.09.04 01:43  Addr Edit/Del Reply

    저같은 경우는 어떤 수를 써도 string으로 받는 건 불가능하더군요. -_-;

    제가 동원할 수 있는 모든 방법을 써 봤지만, 결국 실패했습니다.
    한 문자씩 끊어서 비교. 검사해 가는 수 밖에 없겠더라구요 -_-

    그리고 ... dlbo군의 지적대로, 구조체 배열로 스택을 구현하기 보단 차라리 스택을 처리할 수 있는
    루틴을 따로 함수로 작성해서 코딩하는 것이 훨씬 나은 방법이라 생각됩니다.

    물론, 꽤 아슬아슬하겠지만 말이죠 -_-;;

    제 저번 솔루션이 그런 식이었습니다만... 전북대학교 동아리 ALPS의 솔루션과 90% -_-;; 흡사하기 때문에...
    여기에 올리기엔 무리가 있습니다. - 깜짝 놀랬어요 ㄱ- -

    다른 방법을 강구해서 어떻게든 풀어보도록 하죠.

  2. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.04 21:35  Addr Edit/Del Reply

    EOF 처리방법 알려준대로 해서 끝냄//

    그리고 gets가 4 (2(2()())까지 받아들인다고 말했는데 저 소스가 그렇게 짜여있진 않네//
    3 (3()())을 입력하고 엔터치는 순간 while문에서 튕겨나가지;

    SIZE 300이 불만이면 그건 그냥 늘여놓으면 되는 일.

prev 1 next