글 읽기 - 틀린 부분을 모르겠습니다

zmtn94 6년 전 0

어디가 잘못 된건지 모르겠네요

도와주세요 고수님들......

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
long long res;
long long solve(long long n, long long r, long long c) {
 
    if (n == 2) {
        if (r == 1 && c == 1)
            return 1;
        else if (r == 1 && c == 2)
            return 2;
        else if (r == 2 && c == 1)
            return 3;
        else if (r == 2 && c == 2)
            return 4;
    }
    int mid = n / 2;
    if (r > mid&&c > mid) { /*4*/
        res =(res+(n*n * 3) / 4) + solve(mid, r - mid, c - mid);
    }
    else if (r > mid&&c <= mid) { /*3*/
        res =(res+(n*n * 2) / 4) + solve(mid, r - mid, c);
    }
    else if (r <= mid&&c <= mid) { /*2*/
        res =(res+(n*n * 0) / 4) + solve(mid, r, c);
    }
    else if (r <= mid&&c > mid) { /*1*/
        res =(res+(n*n * 1) / 4) + solve(mid, r, c - mid);
    }
    return res;
};
int main()
{
    long long N, r, c; //row, col
    cin >> N >> r >> c;
        //1,2,3,4사분면
        long long answer = 0;
        res = 0;
        if (N == 1) {
            if (r == 0 && c == 0) {
                cout << 0<<endl;
            }
            else if (r == 0 && c == 1) {
                cout << 1<<endl;
            }
            else if (r == 1 && c == 0) {
                cout << 2<<endl;
            }
            else if (r == 1 && c == 0) {
                cout << 3<<endl;
            }
        }
        else {
            long long n = (long long)pow(2, N);
            // N <= 15
            // n <= 32768
            // 1073741824
            answer = solve(n, r + 1, c + 1);
            --answer;
            cout << answer << endl;
        }
    return 0;
}

Juno 6년 전 1

else if (r == 1 && c == 0) {
cout << 3<<endl;

}

r == 1 && c == 1로 바꾸셔야겠네요

zmtn94 6년 전 0

와... 이런실수를... 감사합니다

말씀해주신거 고쳤는데도 틀렸습니다라고 나오네요 ㅠㅠㅠㅠ.ㅠ

Juno 6년 전 1

알고리즘에 문제가 있는데 컴파일러에 따라 답이 나올 수도 있고 답이 안 나올 수도 있는 것 같습니다.

res = res + ... + solve() 구문의 우변에서 res를 먼저 참조할 수도 있고, solve를 수행한 뒤 res를 참조할 수도 있습니다.

전자의 경우 참조된 res는 항상 0이지만, 후자의 경우 res가 재귀적으로 누적되어 0이 아닌 값을 갖게 됩니다. 이 누적된 값을 또 리턴해서 누적하니 누누적(?) 되는겁니다.

일단 전자의 경우가 답이 되고요. 누누적(?)되지 않게 알고리즘을 수정해보시길..;;

zmtn94 6년 전 0

@junodeveloper

말씀대로 후자의 경우 처럼 res가 재귀적으로 누적되어 있었습니다.

논리적으로 중요한 문제 알려주셔서 감사합니다.

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std; 
long long solve(long long n, long long r, long long c) {
	long long tmp = 0;
	if (n == 2) {
		if (r == 1 && c == 1)
			return 1;
		else if (r == 1 && c == 2)
			return 2;
		else if (r == 2 && c == 1)
			return 3;
		else if (r == 2 && c == 2)
			return 4;
	}
	int mid = n / 2;
	if (r > mid&&c > mid) { /*4*/
		//res = (res + (n*n * 3) / 4) + solve(mid, r - mid, c - mid);
		tmp = tmp + solve(mid, r - mid, c - mid) + ((n*n * 3) / 4);
	}
	else if (r > mid&&c <= mid) { /*3*/
		//res = (res + (n*n * 2) / 4) + solve(mid, r - mid, c);

		tmp = tmp + solve(mid, r - mid, c ) + ((n*n * 2) / 4);
	}
	else if (r <= mid&&c <= mid) { /*2*/
		//res = (res + (n*n * 0) / 4) + solve(mid, r, c);
		tmp = tmp + solve(mid, r , c) + ((n*n * 0) / 4);
	}
	else if (r <= mid&&c > mid) { /*1*/
		//res = (res + (n*n * 1) / 4) + solve(mid, r, c - mid);
		tmp = tmp + solve(mid, r, c - mid) + ((n*n * 1) / 4);
	}
	return tmp;
};
int main()
{
	long long N, r, c; //row, col
	cin >> N >> r >> c;
	//1,2,3,4사분면
	long long answer = 0; 
	if (N == 1) {
		if (r == 0 && c == 0) {
			cout << 0 << endl;
		}
		else if (r == 0 && c == 1) {
			cout << 1 << endl;
		}
		else if (r == 1 && c == 0) {
			cout << 2 << endl;
		}
		else if (r == 1 && c == 1) {
			cout << 3 << endl;
		}
	}
	else {
		long long n = (long long)pow(2, N);
		// N <= 15
		// n <= 32768
		// 1073741824
		answer = solve(n, r + 1, c + 1);
		--answer;
		cout << answer << endl;
	}
	return 0;
}

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

문제

문제

출처

ICPC

틀린 부분을 모르겠습니다

zmtn94 6년 전 0

Juno 6년 전 1

zmtn94 6년 전 0

Juno 6년 전 1

zmtn94 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말