https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 입출력을 꼭 sys.stdin.readline 으로 바꿔주어야 시간초과가 안난다 !! 그리고 pypy3로 통과했다 i 부터 j 까지의 수열이 펠린드롬인지 확인해야 하는데 미리 dp 테이블을 채워준다. 펠린드롬 수열의 경우 길이가 1인경우 펠린드롬이므로 dp[i][i] = 1 을 채워준다. if start == end: # 자기 자신인 경우 무조건 1 임 dp[start][end] = 1 길이가 2인경우 수열 두가지만 확인하면 되는데, ..
DP문제
https://www.acmicpc.net/problem/22869 22869번: 징검다리 건너기 (small) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 징검다리 건너기 (large) 문제와 거의 동일하게 풀었다. 다만 마지막에 dp[-1] 칸이 값이 k보다 작거나 같은지 확인해주면 된다. import sys input = sys.stdin.readline n, k = map(int, input().split()) array = list(map(int, input().split())) I..
https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 쉽지않은 계단수 문제였따 .. 여기서 (0-9)는 맨 끝자리수이고 N은 문제에서와 같이 자리수를 뜻한다. 규칙은 이렇게 각 끝자리수의 개수를 대각선 방향 왼쪽 위 + 대각선 방향 오른쪽 위 를 더하면 구할 수 있다. 즉, dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 라는 식이 나온다 !!! 끝자리 수가 0, 9일때는 각각 한쪽방향의 대각선에서만 존재하니까 그 수를 그대로 옮겨오면 된다. 위의 그림에서는 파란 선을 참고! 자리수가 1일때 (한자리수)일 때는 직접 초기화를 해주어야 한다. ..
