랜덤다이스로 걸려서 푼 문제.(머지않아 플레도 도전해봐야지..)
새로 수열을 정의하고, 여러가지 명령들을 주어서 같이 구현해야 할 것이 많았던 문제였다.
내 풀이의 코드는 다음과 같다.(공부를 하고 싶은 사람이 있을 것 같아서 사진에서 보이듣이 틀렸던 케이스의 코드를 그대로 적어두었다.)
from sys import stdin
seq = [0,1,1]
sum_seq = [0,1,2]
num = 1000000007
init_num = 2
for i in range(3,1000001):
nex = (seq[-1]*(2+init_num))%num
sum_seq.append((sum_seq[-1]+nex)%num)
seq.append(nex) # ! --> 요거 계산수가 문제인데..
init_num = (init_num*2)%num
# print(seq[:15])
# print(sum_seq[:15])
case = int(stdin.readline().strip())
def sec_ord(numb):
cnt = 0
while True:
if numb%2 != 0:
return cnt # 이거도 업데이트가 가능할텐데... X --> at most O(16)
numb = numb//2
cnt += 1
for _ in range(case):
arr = stdin.readline().strip()
if arr.startswith('4'):
order,one,i = map(int,arr.split())
# if len(seq)-1 < i:
# for k in range(len(seq),i+1):
# seq.append((seq[-1]*(2+2**(k-2)))%num) # index update.
print((one*seq[i])%num)
continue
order,one,i,j = map(int,arr.split())
if i>j:
i,j = j,i
# if len(seq)-1 < max(i,j):
# for k in range(len(seq),max(i,j)+1):
# seq.append((seq[-1]*(2+2**(k-2)))%num) # index update.
if order == 1: # a_i
print((one*seq[i])%num)
elif order == 2: #a_j를 2로 나눈 count
# sec_ord(one*seq[max(i,j)])
if j <=2:
print(sec_ord(one)) # update1.. one을 2로 나눈 수에 각각의 init a_j들의 2의 지수들은 계산상 j-1와 동일.
else:
print(sec_ord(one)+(j-1)) # update2.. j가 1인 경우와 연산이 곱셈이 아닌 덧셈!!!
elif order == 3: # 이거 로직 맞는데...,,,,ㅠ
print((one*(sum_seq[j] - sum_seq[i-1]))%num)
# update2.. 여기도 one을 곱해줬어야했는데...,,,
# print(sum(seq[i:j+1])%num) # 만약 줄인다면 이거...?이 문제에서는 고려해야 할 사항이 엄청나게 많았다. 첫 번째로 수열 자체가 처음에 이해하기 좀 난해했는데 그냥 결론적으로 잘 더하면 된다는 것이었다.
또한 연속한 수열간에는 다음 점화식이 성립한다.(원리에 대해서는 수식을 보고 직접 알아보길 바람!!)
a_1 = a_2 = k(k는 지정된 상수)
a_{i+1} = (2**(i-2) + 2) * a_{i} 수열을 이해한 후 처음 코드를 구상했을 때는 명령에 따라 큰 수가 들어올 때마다 수열이 업데이트되게 코드를 짰다. 하지만 충분히 큰 수에 대해 제곱 자체도 계산에 상당히 부담이 된다는 점, 그리고 썼다 지웠다하며 남겨지지 않은 여러 요소들 때문에 initial code는 당연히 시간초과가 나왔다.(나중에 보니 3번 계산도 초깃값을 곱해줘야 한다는 것을 빼먹어서 후반에 틀렸습니다의 대부분은 저기서 나온 것 같다. 뒤에 말할 생각이 없어서 미리 써놓는다.)
몇번 고생하면서 안된다는 것을 안 후 생각을 조금 바꿔서 수열을 구상하는 초기에 initial value인 a_1 = 1이라는 조건을 주고, 다음 수열을 구할 때마다 필요한 2**x를 init_num으로 지어주는 등으로 효율을 챙겼더니 그제서야 시간초과가 뜨지 않고 채점이 되더라.(그래봐야 3번 때문에 틀렸지만...)
이후 (3번)누적합자체도 은근 시간이 많이 든다는 점을 고려해 수열을 생성하는 과정에서 누적합을 해주는 배열도 같이 하나 만들어주고, 3번까지 고친 이후 채점을 했더니 성공!!
명령도 그냥 구현했으면 어디서든 아마 시간초과가 나올 가능성이 높았을 것이다. 문제에서 준 명령은 4가지이고, 이를 차례대로 설명해본다.
이 때 (initial value)는 a_1의 값을, 그 뒤에 숫자 i j는 각각
a_i, a_j의 index를 나타낸다.(i<=j로 세팅.) 또 seq는 수열을 배열로 풀어놓은 것이고, sum_seq는 수열의 누적합을 나타낸 것이다.(당연하게도, 정말정말 큰수가 되기 때문에 각 수는 모두 num = 1000000007로 나누어진 수만 넣어놓았다. 세세한 계산의 원리는 문제를 푸는 당사자가 직접 생각해보면 좋을 것 같아 과제로 남겨놓는다. 사실은 귀찮아서이다.)
-
1 (initial value) i j: 1번 명령은 점화식을 생각하지 않았을 경우 쓰기에 어려운 명령이었다. but 점화식을 안다면a_1 * seq[i]를num으로 나눠주기만 하면 clear! -
2 (initial value) i j: 2번 명령도 마찬가지로 점화식을 잘 생각해봐야 하는 명령이었다. 최소공배수의 2의 지수를 출력하는 명령인데 최소공배수야 1번 명령과 마찬가지로 그냥a_j를 기준으로 생각하면 된다. 하지만 이건 어쩌면 함정카드에 가까운 결론이고, 역시 수열을 통해 푸는 문제인데, 초깃값을 제외하고 생각한다면, 각 수열에 2의 지수가 들어가있는 갯수는 2번째 이후의 숫자에서 '수열의 순서 - 1'이라는 결과를 얻을 수 있다.(이를 계산으로 때려박는다고 생각해보면 명령당으로 따져봐도 좀 무지막지한 메모리와 계산량이 필요하지 싶은데num으로 나누지 않고a_100을 계산해본 결과 그대로 콘솔창이 꽉찼다.. 해보지는 않았지만 수열을 생성하는 과정에서 수열을 계산할 때num으로 나누는 과정을 생략하게 된다면 시간초과는 둘째 문제이고, 메모리 초과가 나오지 않았을까..?..) -
3 (initial value) i j: 누적합 문제. 이거때문에 시간초과가 난 것 같다고 의심하며 누적합 수열sum_seq까지 만들어가며 계산을 했지만 결론은 초깃값 이슈...,,,, 계산 원리는 위에 말했던대로 생략한다.(2번과는 다르게 사칙연산 수준에서 이유를 알 수 있다.) -
4 (initial value) i: 유일하게 가장 쉬운 명령. 그냥(a_1 * seq[i])%num을 구하면 된다.
1~3번째 명령들은 4개 split을 했을 때 4개의 변수를 받지만, 4번째 명령은 3개의 변수를 받는데 이를 굳이 하나로 묶기 싫어서 4번 명령인지를 먼저 확인하고 4번이면 명령에 따라 처리 후 continue, 아니라면 변수 4개로 split해서 받은 후 각 명령에 따라 처리하는 방식으로 코드를 구현했다.
결론 : 생각도 이리저리 많이 해야했고, 푸는 과정 자체도 즐거운(?) 재미있는 문제였다.(역시 공부는 즐거워!)
만약 누군가 보신다면 잘 참고해보시길 ㅎㅎ
