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

작성한 질문수

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

2-E와 분할정복(Divide & Conquer)

2-E 질문있습니다

작성

·

94

0

http://boj.kr/5a173f75eb094fd0a5ffef8f9387af5e

다음과 같이 코드를 작성했습니다.

백준에서 56%정도 됬을때 틀렸다고 나오는데

제가 생각한 틀린 이유로는

무조건 ()를 추가한다. 전체가 압축이 가능한 경우에도
전체를 검사하고 4등분을 해야하는데 4등분한 것부터 검사한다.

인거 같습니다. 혹시 이 이유로 틀린게 맞을까요??
저기서 조금 수정해서 답이 나오려면 어떤부분을 어떻게 고쳐야 할까요??

c++코딩-테스트

답변 1

0

지식공유자

안녕하세요 현우님 ㅎㅎ

무조건 ()를 추가한다. 전체가 압축이 가능한 경우에도

>> 네 맞습니다.

전체를 검사하고 4등분을 해야하는데 4등분한 것부터 검사한다.

>> 네 맞습니다. 로직자체가 좀 꼬인 것 같습니다. ㅠㅠ

어떻게 고쳐야 할까요??

>>

go() 함수부분을 이렇게 고치시면 됩니다.

지금 검사하는 부분이 같은지 확인 -> 같으면 () 없이 리턴 if check -> return
다르다면

void go(int sx,int ex,int sy,int ey){
	int dx[3] = {sx, (sx + ex) / 2, ex};
    int dy[3] = {sy, (sy + ey) / 2, ey};	
	
	ret+="(";

앞의 코드처럼 무조건(을 넣어서 하는 로직.+ for문 돌리면서 실행

하시는 것으로 바꾸시면 될 것 같습니다.

참고로 반례는 다음과 같습니다.

1 1

현우님코드 : (1111)

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

작성한 질문수