dayg502   2년 전

3. 가능하면 쉬운 문제부터 풀어야 한다. 조건이 애매하게 보여서요.

만약 아래와같은 테스트케이스의 경우

100 1
100 1

정답이 아래 두개중 무엇이되어야할까요?

2 3 4 ... 99 100 1   //A
100 1 2 3 4 ... 99   //B

A의 경우 2~100 번이 1번보다 어려운문제인데 빨리풀었으니 3번 규칙을 99번 위반하고

B의 경우 100이 1~99번보다 어려운문제인데 빨리 풀었으니 마찬가지로  3번 규칙을 99번 위반했는데요

문제의 조건이 충분치 않다고 느껴집니다.

'1부터 100까지의 문제는 난이도 순으로 나열되어있다.'

'100번을 먼저 풀면 1번이 쉬워진다.'

이 두개가 사실은 상충하는데요,

'100번이 사실은 1, .. 99번보다 쉬운거였음' -> 100번 문제의 난이도에 대한 재평가 -> 100번을 1~99번보다 나중에 풀기 -> B번

'1번이 사실은 1, .. 99번보다 어려운거였음' -> 1번 문제의 난이도에 대한 재평가 -> 1번을 2~100번보다 나중에 풀기 -> A번


이 둘중하나를 명시해 줘야만 문제조건이 완성될것같습니다.

요는, 문제에 다음 구절을 수정해야 할것같습니다.

> 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 

> (A번이 답일 경우) 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 5번 문제를 풀고 나면 3번 문제가 쉽게 풀린다거나 하는 식이다. 이는 3번 문제가 사실은 어려운 문제였다는 사실도 된다. 이에 따라 민오는 3번에 대한 난이도평가를 다시 하도록 한다. 3번은 사실 5번보다 어려운 문제였고, 5번의 난이도에 대한 평가는 유지한다.

> (B번이 답일 경우) 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 5번 문제를 풀고 나면 3번 문제가 쉽게 풀린다거나 하는 식이다. 이는 5번 문제가 사실은 쉬운 문제였다는 사실도 된다. 이에 따라 민오는 5번에 대한 난이도평가를 다시 하도록 한다. 5번은 사실 3번보다 쉬운 문제였고, 3번의 난이도에 대한 평가는 유지한다.

yukariko   2년 전

문제 번호가 작을 수록 쉽다고 명시되어 있으니 후자가 맞을것 같습니다.

yukariko   2년 전

아니네요 제대로 읽어보니 전자가 맞네요

3번 조건에 따라 가장 쉬운 1을 풀려고 했으나 2번 조건에 따라 100을 먼저 풀어야 했고

3번 조건에 따라 그 다음 가장 쉬운 2를 푸는것이 조건상 맞는것 같습니다.

dayg502   2년 전

저는 일단 알고리즘 세우는 입장에서 '풀수있는 가장 작은 문제부터 푼다' 라는 생각으로 접근하려고 했는데요 다른 질문들보니 그렇게 하는게 맞는거같구요.

즉슨 전자가 맞는거같습니다. 문제 풀어보고 돌아올게요.

dayg502   2년 전

요는, 문제의 조건이 충분하지 않다는 점입니다. 

풀어야지 생각하고 풀려면 대충 이런의미겠구나 하고 풀리긴하는데 엄밀히는 조건이 명확하지 않은것같아요. 좀더 부연을 해줘야 좋을것같습니다.

yukariko   2년 전

저 역시 문제가 헷갈리긴 하나 조건을 따져보면 부족한 조건은 없어보입니다.

2번 조건이 그 문제의 난이도를 바꾼다고 생각해서 발생한 오류로 보입니다.

dayg502   2년 전

네. '문제를 푸는 순서를 정하는' 관점에서 해석하려고 하는 바람에 문제가 모호하다고 느껴졌네요. '이번에 어떤 문제를 풀지 따져보는데, 이때 먼저풀어야하는 문제가 있는 문제는 풀지 말고, 가장 작은 문제부터 푼다' 는 관점에서 보면 명확하네요.

tjdans6342   1년 전

[CASE A]

100 → 1 을 만족해야 하고 100은 가장 어려운 문제이므로 `2 3 4 ... 99 100 1` 가 정답이다.

[CASE B]

100 → 1 을 만족해야 하고 1이 가장 쉬운 문제이므로 `100 1 2 3 ... 98 99` 가 정답이다.

두 가지 경우로 해석될 수 있다고 생각했는데 질문글 보고 이해하고 갑니다!

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