반례를 찾지 못하겠습니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

5-X

해결된 질문

작성

190

http://boj.kr/6258c1ff85134915a0cdfa47b6c7266f

우선 저도 dfs 형식으로 cctv의 개수만큼 0000부터 3333까지 방향을 바꿔가면서 모든 경우를 탐색하는 완탐을 구현했습니다.

다만 다른 부분이 있다면, 비트 마스킹을 활용했다는 점과 전역변수 사용을 하지 않았기에 원복을 딱히 시키지 않았다 인데, 시간초과도 아닌 틀렸습니다가 나옵니다.ㅠㅠ

조언 주시면 감사하겠습니다.

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 Maruche님 ㅎㅎ

코드 잘 짜셨네요 ㅎㅎ

            for (int d=0; d<dir; ++d)
            {
                type = type << 1;
                if (type & 0B10000){
                    type |= 0B0001;
                    type &= ~(1<<5);
                }
            }

특히 이부분이 예술이네요.

원래 비트연산 기반으로 할 때 << 를 쓸 때 주의할 점은 해당 연산을 계속할 경우 오버플로가 발생하기 때문에 그걸 적절히 막아주는게 필요함 + 해당 부분을 기반으로 돌리는 부분.. 훌륭합니다.

제가 답변을 이렇게 늦게 드린 이유는 2일동안 디버깅도 해보고.. 이 코드 기반으로 풀려고 시간도 많이 들이고 반례도 만들어서 넣어보는 노력을 하다가 그랬는데요.

저또한 반례를 못찾는 것 같습니다.

도움이 못되어서 죄송합니다....

감사합니다.

Maruche

질문자

앗 칭찬 감사합니다.. 엄밀히 따지자면 저 type은 지역변수라 dir이 최대 4인 만큼 int형에서 오버플로우가 날 이유는 없어보이지만 그래도 혹여나 싶어서 넣어본건데 원인은 아니었던 것 같네요ㅋㅋ

항상 답이 없는(?) 어려운 질문 드려도 받아주셔서 제가 더 감사합니다! 마냥 잘못된 방법이 아니었다고 확인만 받아도 큰 도움이 되네요. 감사합니다!

인프런 커뮤니티 질문&답변

반례를 찾지 못하겠습니다.