"0719 Even Odd Query"의 두 판 사이의 차이
ph
잔글 |
잔글 |
||
| 4번째 줄: | 4번째 줄: | ||
$$ [ \dots , 2 , 0, 2, 4, \underbrace{6, 4, 3, 7}_{\large{6^{4^{3^7}}}}, 1, 2, 4, 7, 0, 9, 8, 4, \dots ] $$ | $$ [ \dots , 2 , 0, 2, 4, \underbrace{6, 4, 3, 7}_{\large{6^{4^{3^7}}}}, 1, 2, 4, 7, 0, 9, 8, 4, \dots ] $$ | ||
| − | 늘 그렇듯 이런문제도 값을 실제로 구할 필요는 없고 홀짝만 구하면 된다. 문제에 보면 아래 함수의 리턴값을 구하는 것이라고 되어 있는데 위 그림에서 설명한 것과 같다.(아래에서 <c>x, y</c>가 위의 그림에서 시작과 끝 index다.) | + | <del>늘 그렇듯 이런문제도</del> 값을 실제로 구할 필요는 없고 홀짝만 구하면 된다. 문제에 보면 아래 함수의 리턴값을 구하는 것이라고 되어 있는데 위 그림에서 설명한 것과 같다.(아래에서 <c>x, y</c>가 위의 그림에서 시작과 끝 index다.) |
<pre>find(int x,int y) | <pre>find(int x,int y) | ||
{ | { | ||
| 12번째 줄: | 12번째 줄: | ||
}</pre> | }</pre> | ||
| − | 어찌어찌해서 여러 경우를 나누는 방법으로 해결하기는 했는데, < | + | 어찌어찌해서 여러 경우를 나누는 방법으로 해결하기는 했는데, <del>이것도 늘 그렇듯이</del> 모법답안이 훨씬 더 간결하다. 설명은 다음과 같고, |
<blockquote>순서대로 아래 세가지 조건을 확인한다. | <blockquote>순서대로 아래 세가지 조건을 확인한다. | ||
<ol><li>A[a]가 홀수이면 A[b]와 무관하게 답은 홀수다.</li> | <ol><li>A[a]가 홀수이면 A[b]와 무관하게 답은 홀수다.</li> | ||
<li>a와 b가 같으면 답은 짝수다.(a가 홀수인 경우는 위 1에서 이미 처리했다)</li> | <li>a와 b가 같으면 답은 짝수다.(a가 홀수인 경우는 위 1에서 이미 처리했다)</li> | ||
| − | <li>A[a+1] \(=0\)이면 답은 홀수다(모든 수의 \(0\)승은 \(1\)이니까)<ref>이거 사실 그짓말. 참고할만한 한글 자료로는 [http://terms.naver.com/entry.nhn?docId=3567048&cid=58944&categoryId=58970 네이버 캐스트에 관련글]이 있다. 편의상 1로 놓아도 그럴듯 하다는 근거로는 나무위키의 [https://namu.wiki/w/0의%200제곱 0의 0제곱]이 볼만 하다. < | + | <li>A[a+1] \(=0\)이면 답은 홀수다(모든 수의 \(0\)승은 \(1\)이니까)<ref>이거 사실 그짓말. 참고할만한 한글 자료로는 [http://terms.naver.com/entry.nhn?docId=3567048&cid=58944&categoryId=58970 네이버 캐스트에 관련글]이 있다. 편의상 1로 놓아도 그럴듯 하다는 근거로는 나무위키의 [https://namu.wiki/w/0의%200제곱 0의 0제곱]이 볼만 하다. <del>영문자료는 아예 찾아보지도 않았지롱</del> |
<br/> | <br/> | ||
\(0^0=0\)으로 놓고 풀어도 테스트케이스는 통과하는 것으로 봐서 이에 대한 처리도 해놓았나보다. 무서운놈들.</ref></li> | \(0^0=0\)으로 놓고 풀어도 테스트케이스는 통과하는 것으로 봐서 이에 대한 처리도 해놓았나보다. 무서운놈들.</ref></li> | ||
| 28번째 줄: | 28번째 줄: | ||
return 0; | return 0; | ||
}</pre> | }</pre> | ||
| − | 저 세 조건의 순서를 바꾸면 처리하기가 훨씬 더 복잡해진다. < | + | 저 세 조건의 순서를 바꾸면 처리하기가 훨씬 더 복잡해진다. <del>내가 그렇게...</del> |
find함수를 아래와 같이 하면 훨씬 더 보기 좋은것 같은데, | find함수를 아래와 같이 하면 훨씬 더 보기 좋은것 같은데, | ||
2017년 7월 20일 (목) 00:32 판
아래와 같이 임의의 (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
}
어찌어찌해서 여러 경우를 나누는 방법으로 해결하기는 했는데, 이것도 늘 그렇듯이 모법답안이 훨씬 더 간결하다. 설명은 다음과 같고,
순서대로 아래 세가지 조건을 확인한다.
- A[a]가 홀수이면 A[b]와 무관하게 답은 홀수다.
- a와 b가 같으면 답은 짝수다.(a가 홀수인 경우는 위 1에서 이미 처리했다)
- A[a+1] \(=0\)이면 답은 홀수다(모든 수의 \(0\)승은 \(1\)이니까)[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
ㅇㅇ
- ↑ 이거 사실 그짓말. 참고할만한 한글 자료로는 네이버 캐스트에 관련글이 있다. 편의상 1로 놓아도 그럴듯 하다는 근거로는 나무위키의 0의 0제곱이 볼만 하다.
영문자료는 아예 찾아보지도 않았지롱
\(0^0=0\)으로 놓고 풀어도 테스트케이스는 통과하는 것으로 봐서 이에 대한 처리도 해놓았나보다. 무서운놈들.