mongsiry013   2년 전

어려운 문제는 아닌거 같은데 어디서 틀렸다는 건지 못찾고 있어요 ㅠ

채점 25%에서 틀림 판정을 받네요

틀린 케이스 좀 알려주세요ㅠ

알고리즘은 그리드 방법을 사용합니다.

사용되는 알고리즘은 다음과 같습니다.

1. 각 빈 자리마다 value 값 설정

   value값이 의미하는 것은 해당 자리에 학생을 앉힐 경우 그로 인해 사용할 수 없게 되는 빈 자리의 수를 의미한다.

2. value 값이 가장 작은 빈 자리를 선택

3. 선택 된 자리에 학생을 앉힘.

   -  '.' 를 'O'로 변경.  'O'는 학생이 앉은 자리를 의미.

   - 해당 자리에 학생을 앉힘으로써 주위에 다른 학생들이 못 앉게 되는 자리를 'X'로 변경.  

     'X'는 컨닝 때문에 학생이 못 앉게 되는 자리 또는 책상이 부셔져서 학생이 못 앉게 되는 자리를 의미.

 4. 빈 자리가 남아 있지 않을 때까지 1번부터 다시 반복.

변수 설명 :

 room - room[i][j]는 i번째 줄 j번째 열의 자리를 의미. 빈자리 : '.', 학생이 앉은 자리 'O', 학생이 앉을 수 없는 자리 'X'

 Help  - 각 빈자리의 value값을 저장하는 리스트. [i, j, value] 형태로 저장. value값을 기준으로 정렬하여 value값이 최소인 자리를 찾음.

 empty_space - 현재 빈 자리의 개수

 student_space - 현재 학생이 앉은 자리의 개수

appa   2년 전

X . .

. X X
이런 경우에 (1,2)번째랑 (1,3)번째랑 value값이 같은데 답은 (1,3)이랑 (2,1)을 골라야하는 2가 됩니다.

이처럼 value값이 같은 자리가 여러 개일 경우에 명백히 오류가 나며, value값이 작은 것을 고른 것이 부분 문제의 해가 될 지는 모르나, 그 부분 문제의 해가 전체 해에 영향을 끼치지는 않으므로 알고리즘의 정확성에서 문제가 생깁니다.

이 문제는 bitmask dynamic programming이나 maximum flow(network flow)알고리즘으로 해결할 수 있습니다.

appa   2년 전

또 다른 풀이가 있을 지는 모르나 위의 2가지 솔루션으로는 제가 Accepted를 받았습니다.

mongsiry013   2년 전

X..

.XX

인 경우 (1,2)번째 value 값은 2, (1,3)번째 value값은 1입니다.

(1,2)에 학생을 앉힐 시, (1,3)과 (2,1)에는 다른 학생을 앉힐 수 없으므로 value값이 2가 되고

(1,3)에 학생을 앉힐 시, (1,2)에는 다른 학생을 앉힐 수 없으므로 value값이 1이 됩니다.

해당 소스코드 실행 결과 2가 나옵니다.

appa   2년 전

아 그렇군요. 앉히는 것과 앉는 것을 반대로 이해했네요. 그런데 말씀드린대로 value값이 같은 경우에는 확실히 문제점이 생길거에요.

appa   2년 전

1

10 10

.X.X...X..

.X..X.....

X.X.......

.X.X......

X...X.....

.X.X...X..

.X..X.....

X.X.......

.X.X......

X...X.....
이 경우에 답은 42인데 40을 출력하시네요.

appa   2년 전

1

5 10

.X.X...X..

.X..X.....

X.X.......

.X.X......

X...X.....
이 경우에 답이 21인데 20을 출력하시는군요.

appa   2년 전

1

5 8

.X...X..

..X.....

X.......

.X......

..X.....
이 경우에 답이 18이신데 17을 출력하시고
1

5 7

X...X..

.X.....

.......

X......

.X.....
이 경우에는 답이 17인데 17을 출력하십니다. 맨 왼쪽의 열만 지웠는데 문제가 생겼네요. 참고하시길 바라요.

mongsiry013   2년 전

정말 감사합니다!!

다시 한번 코드를 작성해보아야겠네요

함부로 탐욕알고리즘을 사용하면 안되는군요

appa   2년 전

오 맞으셨네요. 어떻게 푸신거죠?

mongsiry013   2년 전

알고리즘을 다시 작성하였습니다.

계산해보니까 한줄에 나올수 있는 최대 경우의 수가 144개 뿐이더군요.(부셔진 책상이 하나도 없는 row의 경우)

만약 첫째줄과 셋째줄이 어느 값으로 정해져있다면 두번째 줄은 한가지 경우밖에 되지 않겠죠.

그래서 첫째줄과 셋째줄에 모든 경우의 수를 계산하면 최대 144*144개 뿐입니다.

그럼 셋째줄 144개의 경우에 대해 학생이 앉을 수 있는 최대 경우의 수를 구할 수 있습니다.

그리고 다섯번째 줄의 모든 경우의 수를 생각하여 또 다시 최대 144*144번의 반복을해서 넷째줄을 정하고 하는 방법입니다.

appa   2년 전

와우... 신기하네요...

pauline   1년 전

hongjun7 님 푸신 방법으로 풀어보려고 하는데 아무리 해도 부서진 책상이 하나도 없는 row의 경우에 대한 최대 경우의 수가 144가 안나오는데 ㅠㅠ

..........

이 경우 제 계산으로는

0명 앉히는 경우: 1개

1명 앉히는 경우: 10개

2명 앉히는 경우: 36개

3명 앉히는 경우: 30개

4명 앉히는 경우:14개

5명 앉히는 경우: 6개

해서 총 97가지 밖에 안나오는데..

어떻게 144가지가 나오는지 알려주실 수 있으신가요? +_+

mongsiry013   1년 전

0번이 맨 왼쪽에 있는 의자, 9번이 맨 오른쪽에 있는 의자라고 할 때 다음과 같은 경우의 수들이 있습니다.


()

(0,)

(1,)

(2,)

(3,)

(4,)

(5,)

(6,)

(7,)

(8,)

(9,)

(0, 2)

(0, 3)

(0, 4)

(0, 5)

(0, 6)

(0, 7)

(0, 8)

(0, 9)

(1, 3)

(1, 4)

(1, 5)

(1, 6)

(1, 7)

(1, 8)

(1, 9)

(2, 4)

(2, 5)

(2, 6)

(2, 7)

(2, 8)

(2, 9)

(3, 5)

(3, 6)

(3, 7)

(3, 8)

(3, 9)

(4, 6)

(4, 7)

(4, 8)

(4, 9)

(5, 7)

(5, 8)

(5, 9)

(6, 8)

(6, 9)

(7, 9)

(0, 2, 4)

(0, 2, 5)

(0, 2, 6)

(0, 2, 7)

(0, 2, 8)

(0, 2, 9)

(0, 3, 5)

(0, 3, 6)

(0, 3, 7)

(0, 3, 8)

(0, 3, 9)

(0, 4, 6)

(0, 4, 7)

(0, 4, 8)

(0, 4, 9)

(0, 5, 7)

(0, 5, 8)

(0, 5, 9)

(0, 6, 8)

(0, 6, 9)

(0, 7, 9)

(1, 3, 5)

(1, 3, 6)

(1, 3, 7)

(1, 3, 8)

(1, 3, 9)

(1, 4, 6)

(1, 4, 7)

(1, 4, 8)

(1, 4, 9)

(1, 5, 7)

(1, 5, 8)

(1, 5, 9)

(1, 6, 8)

(1, 6, 9)

(1, 7, 9)

(2, 4, 6)

(2, 4, 7)

(2, 4, 8)

(2, 4, 9)

(2, 5, 7)

(2, 5, 8)

(2, 5, 9)

(2, 6, 8)

(2, 6, 9)

(2, 7, 9)

(3, 5, 7)

(3, 5, 8)

(3, 5, 9)

(3, 6, 8)

(3, 6, 9)

(3, 7, 9)

(4, 6, 8)

(4, 6, 9)

(4, 7, 9)

(5, 7, 9)

(0, 2, 4, 6)

(0, 2, 4, 7)

(0, 2, 4, 8)

(0, 2, 4, 9)

(0, 2, 5, 7)

(0, 2, 5, 8)

(0, 2, 5, 9)

(0, 2, 6, 8)

(0, 2, 6, 9)

(0, 2, 7, 9)

(0, 3, 5, 7)

(0, 3, 5, 8)

(0, 3, 5, 9)

(0, 3, 6, 8)

(0, 3, 6, 9)

(0, 3, 7, 9)

(0, 4, 6, 8)

(0, 4, 6, 9)

(0, 4, 7, 9)

(0, 5, 7, 9)

(1, 3, 5, 7)

(1, 3, 5, 8)

(1, 3, 5, 9)

(1, 3, 6, 8)

(1, 3, 6, 9)

(1, 3, 7, 9)

(1, 4, 6, 8)

(1, 4, 6, 9)

(1, 4, 7, 9)

(1, 5, 7, 9)

(2, 4, 6, 8)

(2, 4, 6, 9)

(2, 4, 7, 9)

(2, 5, 7, 9)

(3, 5, 7, 9)

(0, 2, 4, 6, 8)

(0, 2, 4, 6, 9)

(0, 2, 4, 7, 9)

(0, 2, 5, 7, 9)

(0, 3, 5, 7, 9)

(1, 3, 5, 7, 9)

총 개수 : 144

mongsiry013   1년 전

hongjun7님께서 253183 소스코드에 댓글 남기셨던데 여기 질문사항에 올라온 코드는 그리디 방법을 써서 오답판정 나왔지만 253183 코드는 그리디 방법이 아닙니다.

그 당시에는 온라인 저지 문제들처럼 알고리즘 문제들을 풀어보는게 처음 시작할 때라 코드를 너무 막 짰었네요.

파이썬도 처음이었구요. 제가 지금 다시 봐도 읽기 힘드네요 ㅠ

상당히 깔끔하지 못한 동적계획법입니다.

그러니까 첫번째, 두번째, 세번째 줄을 연산해서, 세번째 줄의 모든 경우의 수에 대해 최댓값을 저장해 두고

다음 연산으로 세번째, 네번째, 다섯번째 줄을 연산해서 다섯번째 줄의 모든 경우의 수에 대해 최대값을 저장해 두고 하는 식이에요.

지금 생각하면 굳이 세줄씩 잡고 연산할 필요는 없었을 것 같은데.. ㅎㅎ;;

pauline   1년 전


mongsiry013 님 푸신 방법이었는데 제가 아이디를 잘 못 적었네요^^;

답변 감사드립니다~

제가 띄엄띄엄 세었네요

ㅎㅎㅎ

감사합니다!

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