hdnua   9년 전

1. lucky set을 입력받은 후 오름차순 정렬한다.

2. n이 포함된 unlucky 구간의 최소, 최대 값을 구한다.

3. n을 기준으로 두 파트로 나누어 각각의 경우의 수를 구하고 서로 곱한 후 1을 뺀다. (자기 자신)


아래는 이 생각을 표현하는 예제이고, 출력도 올바르게 나온다고 생각합니다.

아이디어 자체가 틀리던지, 놓친 입력이 있던지 할 텐데 뭐가 문제일까요?


/*

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

[case 1]

2

1 7

4

> n = 4

(mid - prev)

2 3 4

3 4

4

(last - mid)

empty

5

5 6

(result)

2 3 4

2 3 4 5

2 3 4 5 6

3 4

3 4 5

3 4 5 6

4 -> x

4 5

4 5 6

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

[case 2]

2

1 7

2

> n = 2

(mid - prev)

2

(last - mid)

empty

3

3 4

3 4 5

3 4 5 6

(result)

2 -> x

2 3

2 3 4

2 3 4 5

2 3 4 5 6

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

[case 3]

2

1 7

6

> n = 6

(mid - prev)

2 3 4 5 6

3 4 5 6

4 5 6

5 6

6

(last - mid)

empty

(result)

2 3 4 5 6

3 4 5 6

4 5 6

5 6

6 -> x

*/

yukariko   9년 전

2

1 7

1

의 경우 0이 답입니다.

현재소스는 돌려보진않았지만

-1을 출력할것같아요.

hdnua   9년 전

아래 소스는 조언을 받아 그 부분을 수정한 코드입니다.

2 1 7 1 -> 0

2 1 7 7 -> 0

2 3 7 2 -> 0

이 세 입력에 대해 모두 잘 동작하는데 아직도 문제가 있을까요?

yukariko   9년 전

2

3 7

2

의 답은 [1,2]로 1이 맞습니다.

고쳐야 할것은 n == lucky[i] 일때만 이구요,

위 소스에서 잘못된 점은 lucky 배열을 정렬할 때, index를 l 까지 주었기 때문에 l+1까지 정렬을 해야 합니다.

즉, 고쳐야 할 qsort 의 코드는 아래와 같습니다.

hdnua   9년 전

명쾌하네요. 매번 좋은 답변 얻어가요. 감사합니다!

댓글을 작성하려면 로그인해야 합니다.