오늘의 주제도 동적계획법
문제
입력과 출력
코드
class Solution:
def divisorGame(self, n: int) -> bool:
cnt=0
while n!=1:
n-=1
cnt+=1
if cnt%2==0:
return False
else:
return True알고리즘
n을 1씩 빼면서(한칸씩 이동하면서)
n이 1이 될때까지 뺴준다.
뺄때마다 cnt를 1씩 더해주고
이 수가 짝수이면 Bob이 이기는 것이므로 False를 반환하고
홀수이면 Alice가 이기는 것이므로 True를 반환한다.
회고
사실은 n을 나눴을 때 나누어떨어지는 수만큼 이동하는 것인데, 이렇게 하니 런타임이 너무 길어서 1씩 빼줘도 무방할거 같은데 싶어 이렇게 도전해보니 통과되었다.. 뭐지!
그래서 나누어떨어지는 수만큼씩 이동한 코드도 함께 첨부한다.
이 코드는 타 사이트에서 참고한 코드인데
의아했던 부분이 이 코드에서도 x의 첫번째 요소만 빼준다.
class Solution(object):
def divisorGame(self, n:int)->bool:
cnt = 0
while n!=1:
x = []
for i in range(1,N):
if N%i ==0:
x.append(i)
n = n -x[0]
cnt +=1
if cnt%2 ==0:
return False
else:
return True그래서 그냥 1만 빼주는 코드로 시도했더니 허용된것이었다.
그래서 나눠떨어지는 수로 만드는 코드를 여러개 시도해봤는데,
명쾌한 답안이 나오지않았다..
테스트케이스 초반만 통과하고 나머진 통과하지 못하거나 반만 통과하는..
내 생각에는 나눠떨어지는 수로 빼주나 1로 빼서 카운트하나 홀수 짝수는 똑같아서 내 풀이가 통과된거 같은데,,
예를 들어, 6
처음에 2 가져감 cnt=1, n=4
또 2 가져감 cnt=2, n=2
1 가져감 cnt=3, n=1
-> 1씩 빼면 cnt=5
같은 홀수이므로 False
이게 굉장히 애매하다..
예를 들어 6이면 1이 빠지면 5가 되고, 또 얘를 나누어떨어지게 하는 수는 1, 5 그치만 5를 빼면 n=0이므로 결론은 1만 쓴다.
이런 경우에는 2씩 빼주거나 뺄때마다 나누어떨어지는 수를 고려해줘야 하는데,,,
정말 이렇게 구성하는게 맞을까 의문이 든다..
다른 분들의 코드가 올라오면 더 참고해봐야겠다.
