0719 Even Odd Query

문제 링크

아래와 같이 임의의 (semi-positive)배열과 구간을 준다. 그러면 아래 보는 그림과 같이 pow의 중첩값을 구해서 그것의 홀짝을 맞추는 문제. $$ [ \dots , 2 , 0, 2, 4, \underbrace{6, 4, 3, 7}_{\large{6^{4^{3^7}}}}, 1, 2, 4, 7, 0, 9, 8, 4, \dots ] $$

늘 그렇듯 이런문제도 값을 실제로 구할 필요는 없고 홀짝만 구하면 된다. 문제에 보면 아래 함수의 리턴값을 구하는 것이라고 되어 있는데 위 그림에서 설명한 것과 같다.(아래에서 x, y가 위의 그림에서 시작과 끝 index다.)

find(int x,int y)
{
    if(x>y) return 1;
    ans = pow(A[x],find(x+1,y))
    return ans
}

어찌어찌해서 여러 경우를 나누는 방법으로 해결하기는 했는데, 이것도 늘 그렇듯이 모법답안이 훨씬 더 간결하다. 설명은 다음과 같고,

순서대로 아래 세가지 조건을 확인한다.

1. A[a]가 홀수이면 A[b]와 무관하게 답은 홀수다.
2. a와 b가 같으면 답은 짝수다.(a가 홀수인 경우는 위 1에서 이미 처리했다)
3. A[a+1] \(=0\)이면 답은 홀수다(모든 수의 \(0\)승은 \(1\)이니까)

모두 다 해당하지 않으면, 짝수다

코드도 간결하다. 아래가 핵심부분

int find(int x, int y){
    if(A[x]%2) return 1;
    if(x == y) return 0;
    if(A[x+1] == 0) return 1;
    return 0;
}

저 세 조건의 순서를 바꾸면 처리하기가 훨씬 더 복잡해진다. 내가 그렇게...

find함수를 아래와 같이 하면 훨씬 더 보기 좋은것 같은데,

def find(x,y):
    if x>y:
        return 1

    v = find(x+1, y)
    if v == 0:
        return 1

    return a[x] # Isn't this cool?

실제로 해보면,

RuntimeError: maximum recursion depth exceeded

ㅇㅇ

일하기도 싫고, 공부하기도 싫고, 자기도 싫어서 가만히 쳐다보다가 다음과 같이 해서 통과

N = input() 
a = [int(x) for x in raw_input().strip().split()]
Q = input()
def isodd(x,y):
    if x>y:
        return 1
    
    if x<y and a[x+1]==0:
        return 1
    
    return a[x]%2

for i in range(int(Q)):
    x,y = [int(el)-1 for el in raw_input().strip().split()]
    
    if isodd(x,y):
        print 'Odd'
    else:
        print 'Even'

계속 일하기도 싫고, 공부하기도 싫고, 자기도 싫어서 다른 사람이 한 코드를 봤는데 1-base인 배열을 다루는 신박한 방법 발견

A = [0]+A

훌륭하다 ㅎㅎㅎㅎ

blog comments powered by Disqus