1059번 - 좋은 구간
1. lucky set을 입력받은 후 오름차순 정렬한다.
2. n이 포함된 unlucky 구간의 최소, 최대 값을 구한다.
3. n을 기준으로 두 파트로 나누어 각각의 경우의 수를 구하고 서로 곱한 후 1을 뺀다. (자기 자신)
아래는 이 생각을 표현하는 예제이고, 출력도 올바르게 나온다고 생각합니다.
아이디어 자체가 틀리던지, 놓친 입력이 있던지 할 텐데 뭐가 문제일까요?
/*
---------------------------
[case 1]
2
1 7
4
> n = 4
(mid - prev)
2 3 4
3 4
(last - mid)
empty
5
5 6
(result)
2 3 4 5
2 3 4 5 6
3 4 5
3 4 5 6
4 -> x
4 5
4 5 6
[case 2]
> n = 2
3
2 -> x
2 3
[case 3]
6
> n = 6
6 -> x
*/
1
의 경우 0이 답입니다.
현재소스는 돌려보진않았지만
-1을 출력할것같아요.
아래 소스는 조언을 받아 그 부분을 수정한 코드입니다.
2 1 7 1 -> 0
2 1 7 7 -> 0
2 3 7 2 -> 0
이 세 입력에 대해 모두 잘 동작하는데 아직도 문제가 있을까요?
3 7
의 답은 [1,2]로 1이 맞습니다.
고쳐야 할것은 n == lucky[i] 일때만 이구요,
위 소스에서 잘못된 점은 lucky 배열을 정렬할 때, index를 l 까지 주었기 때문에 l+1까지 정렬을 해야 합니다.
즉, 고쳐야 할 qsort 의 코드는 아래와 같습니다.
명쾌하네요. 매번 좋은 답변 얻어가요. 감사합니다!
댓글을 작성하려면 로그인해야 합니다.
hdnua 9년 전 1
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
*/