1014번 - 컨닝
X . .
. X X
이런 경우에 (1,2)번째랑 (1,3)번째랑 value값이 같은데 답은 (1,3)이랑 (2,1)을 골라야하는 2가 됩니다.
이처럼 value값이 같은 자리가 여러 개일 경우에 명백히 오류가 나며, value값이 작은 것을 고른 것이 부분 문제의 해가 될 지는 모르나, 그 부분 문제의 해가 전체 해에 영향을 끼치지는 않으므로 알고리즘의 정확성에서 문제가 생깁니다.
이 문제는 bitmask dynamic programming이나 maximum flow(network flow)알고리즘으로 해결할 수 있습니다.
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가 나옵니다.
정말 감사합니다!!
다시 한번 코드를 작성해보아야겠네요
함부로 탐욕알고리즘을 사용하면 안되는군요
알고리즘을 다시 작성하였습니다.
계산해보니까 한줄에 나올수 있는 최대 경우의 수가 144개 뿐이더군요.(부셔진 책상이 하나도 없는 row의 경우)
만약 첫째줄과 셋째줄이 어느 값으로 정해져있다면 두번째 줄은 한가지 경우밖에 되지 않겠죠.
그래서 첫째줄과 셋째줄에 모든 경우의 수를 계산하면 최대 144*144개 뿐입니다.
그럼 셋째줄 144개의 경우에 대해 학생이 앉을 수 있는 최대 경우의 수를 구할 수 있습니다.
그리고 다섯번째 줄의 모든 경우의 수를 생각하여 또 다시 최대 144*144번의 반복을해서 넷째줄을 정하고 하는 방법입니다.
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
hongjun7님께서 253183 소스코드에 댓글 남기셨던데 여기 질문사항에 올라온 코드는 그리디 방법을 써서 오답판정 나왔지만 253183 코드는 그리디 방법이 아닙니다.
그 당시에는 온라인 저지 문제들처럼 알고리즘 문제들을 풀어보는게 처음 시작할 때라 코드를 너무 막 짰었네요.
파이썬도 처음이었구요. 제가 지금 다시 봐도 읽기 힘드네요 ㅠ
상당히 깔끔하지 못한 동적계획법입니다.
그러니까 첫번째, 두번째, 세번째 줄을 연산해서, 세번째 줄의 모든 경우의 수에 대해 최댓값을 저장해 두고
다음 연산으로 세번째, 네번째, 다섯번째 줄을 연산해서 다섯번째 줄의 모든 경우의 수에 대해 최대값을 저장해 두고 하는 식이에요.
지금 생각하면 굳이 세줄씩 잡고 연산할 필요는 없었을 것 같은데.. ㅎㅎ;;
댓글을 작성하려면 로그인해야 합니다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
mongsiry013 9년 전 1
어려운 문제는 아닌거 같은데 어디서 틀렸다는 건지 못찾고 있어요 ㅠ
채점 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 - 현재 학생이 앉은 자리의 개수