인프런 커뮤니티 질문&답변
작성한 질문수
3-O 질문입니다.
작성
·
293
0
http://boj.kr/f084aebaceb24ec69e9a3306fc036ddb
2주차의 벽세우기 문제처럼
가로선 추가할 수 있는 모든 후보들을 vector에 집어넣고
하나 선택하고 안 되면 2개 선택하고 또 안 되면 세개 선택하는 방식으로 풀었는데
강의에서 말씀해주신대로 모든 경우의 수를 다 따져도 시간 초과가 안 날 거 같은데 시간초과가 납니다
무엇이 문제일까요?
is_valid() 함수는 가로선을 하나 추가했을때 겹치는지 확인하는 함수이고
is_connected() 함수는 하나씩 사다리 타서 문제의 조건 (시작점과 도착점이 같은 것)에 맞는지 확인하는 함수입니다
답변 1
0
안녕하세요 10cm님 ㅎㅎ
전반적으로 잘 짜셨네요. ㅎㅎ
근데요.
if (is_valid(candidates[i].first, candidates[i].second) && is_valid(candidates[j].first, candidates[j].second) && is_connected()) {
return 2;
}이거요. 지금 사다리를 세울 때 ~~~ 그 사다리들만 확인하는 로직아닌가요?
이 문제를 잠시 보시면.
가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다.
이렇게 되어있죠? 즉, 모든 가로선이 서로 연속하거나 접하면 안된다고 되어있는데 해당 부분이 조금 부족한 거 같아요.
그런 부분만 제외한다면 전반적으로 잘 짜셨습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
안녕하세요 10cm님 ㅎㅎ
저 코드 괜찮은데 왜 틀렸지? 저도 좀 자세히 보면서 좀 시간이 걸렸는데요.
10cm님의 코드를 좀 수정했고. 맞았습니다를 받았습니다.
http://boj.kr/d24e0f906b67458688636f104112d522
사실 고친 것은 얼마 없긴 합니다만
그저 틀린 거 좀 고치고 불필요한 코드를 줄였습니다.
combination >> size - 1, size - 2 이런식으로 하셨던데 그렇게 하면 안되구요. 이렇게 하시면 됩니다.
for (int i = 0; i < candidates.size(); i++) {
for (int j = i + 1; j < candidates.size(); j++) {
for (int k = j + 1; k < candidates.size(); k++) {10cm 코드는 매우 훌륭했습니다. 참고로
combination 을 return 1, return 2를 먹이면서 우선순위를 통해
재귀함수를 쓰지 않고 백트래킹을 구현했다는 점.
is_valid 함수를 통해 문제에서 안된다는 이어지는 부분에 대한 로직도 잘 확인한 점.
다 좋았습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
답변 감사드립니다 큰돌님. 말씀 해주신대로 for 문 조건 수정하니 성공했습니다.
그런데 수정하기 전에 시간초과가 났던 이유는 뭘까요?
제가 -1, -2 해준 이유는
예를 들어 배열 arr[5]에서 3개를 선택할 경우
0,1,2
0,1,3
0,1,4
...
2,3,4
결국에 첫 번째 요소(첫번째 for문의 i에 해당)는 arr의 size-2 전에서 멈추고
두번째 요소(두번째 for문의 j에 해당)도 arr의 size-1 전에서 멈추는데
큰 차이는 없지만(사실 안해도 되긴하네요) 이것이 왜 시간초과가 나게하는 요인인지 잘 모르겠네요,,
정성스런 답변 항상 감사드립니다.
안녕하세요 큰돌님 답변 감사합니다.
주어지는 입력에서 연속한 가로선이 존재하지 않는다는 조건이 있다면
새로 추가하는 가로선만 체크한다면 모든 경우를 체크하는 것과 똑같지 않을까요
사실은 처음엔 사다리의 모든 가로선을 체크하는 함수를 만들었는데 시간초과가 떠서
생각해보니 추가하는 가로선만 체크하면 되는 것 같아서 수정했더니
똑같이 시간초과가 뜨더라구요,,
복잡한 질문해서 죄송합니다..