수학과의 개발자 도전기

-문제: https://www.acmicpc.net/problem/1937

규칙을 만족하는 경로를 모아 놓고, 거기서 길이가 최대인 경로의 값을 출력하면 될 것 같은데

경로를 어떻게 설정하는지 몰랐음. 이거는 dfs로 풀어야함(알고리즘 익혀두기)

-정답풀이:

-틀린풀이(두개):

• 초반에 recursionlimit거는 것
• 9번째 줄에 x대신 n 쓰기 
• 12번째 줄에 return 들여쓰기 

• 이렇게 풀었을 때 문제점: (i,j)인덱스를 중심으로 경로를 넣는 것이 아니라, (i,j)값 보다 큰 값들이 모두 들어가서 경로를 표현하는 것이 아니게 됨. -> 깊이우선탐색(dfs) 알고리즘 익히기 

-문제: https://www.acmicpc.net/problem/9655

어려워 보이지만 알고보면 굉장히 쉬운 문제다. 복잡하게 생각하지 말고 문제를 이해하면 됨. 

• 예제에서 주어진 돌이 5개일 때 상근이가 이긴 과정을 생각해 보았을 때 다음과 같다

이때 발견한 것이 한번에 가져가는 돌의 개수가 1개 또는 3개 즉 홀수 이므로 N이 홀수라면 상근이를 거친 후 남은 돌의 개수는 짝수이고, N이 짝수라면 상근이를 거친 후 남은 돌의 개수는 홀수이다. 

• 홀->짝->홀->짝->,,,,->1 :이때 순서인 사람이 이긴다
• 짝->홀->짝->홀->,,,,->1 :이때 순서인 사람이 이긴다

그러다 무심코 N이 4, 즉 짝수일 때를 해봤는데 창영이가 이겼다. 그래서 N이 홀수면 상근이가 이기고, N이 짝수면 창영이가 이기나?하고 코드를 짜봤더니 정답이었다. 문제를 이해하려고 했으면 금방 풀 수 있었던 문제다

-정답풀이:

n=int(input())

if n%2==0:
    print('CY')
else:
    print('SK')

-문제: https://www.acmicpc.net/problem/1890

-정답풀이: 

-틀린 풀이: 

• while로 푸니까 무한루프 돌아서 시간초과 났음
• 새로운 nxn 행렬 만들어서 거기에 경로수 대입하는 걸로 생각하면 됨 
• 한번에 맞힐 수 있던 것 같아서 좀 아쉬운 문제 

-문제: https://www.acmicpc.net/problem/1309

문제를 이해하면 이전 타일문제와 점화식이 동일하다. 그렇게 풀어주면 끝. 풀이 도움없이 풀었던 문제 

-정답풀이:

• S(0)=1,S(1)=3,S(2)=7,S(3)=17,S(4)=41 
• 위 값들로 얻은 점화식은 다음과 같다
• S(i)=2*S(i-1)+S(i-2)