흙금이네 블로그

아이디어 동적 계획법을 이용해 각 칸에서 이동할 수 있는 칸의 경우의 수를 증가시켜 나간다. 풀이 #1 (Python) 게임판의 수를 2차원 리스트 board에 저장하고, 이동 경로의 수를 저장하는 0으로 채워진 2차원 리스트 dp를 생성한다. board의 가장 오른쪽 아래 칸과 dp의 가장 왼쪽 위 칸에 각각 1을 저장한다. board의 가장 오른쪽 아래 칸 값을 1로 바꿔 해당 칸 dp에 해당 칸 경로의 수를 더하는 것을 막는다. 이중 for문에서 현재 칸 (i, j)에서 이동할 수 있는 칸 (i+board[i][j], j)와 (i, j+board[i][j])의 dp에 현재 칸 경로의 수를 더한다. import sys input = sys.stdin.readline def solution(): N =..

아이디어 누적합으로 S에서 홀수 원소들을 최대 K번 삭제한 연속된 짝수 수열의 길이를 구한다. 풀이 22857번 가장 긴 짝수 연속한 부분 수열 (small)의 풀이 #2와 같다. 리스트 arr에는 홀수 원소로 구분된 짝수로 이루어진 수열의 길이를 누적합으로 저장한다. for문에서 S의 각 원소가 홀수면 리스트 arr에 arr의 마지막 값을 다시 추가하고, 짝수면 arr의 마지막 값을 1 증가시킨다. arr의 K 번째 원소까지는 앞의 홀수 원소들을 모두 제거할 수 있으므로 그 마지막 값을 결과값 res에 저장한다. for문에서 K개의 홀수 원소를 제거한 짝수로 이루어진 수열 길이의 최댓값으로 res를 갱신해 나간다. arr의 길이 M이 K보다 작다면 결과값 res에는 누적합의 최댓값이 저장되고, for문..

아이디어 S의 홀수 원소로 구분된 연속된 짝수 수열의 길이를 구한 후 그 길이의 합의 최댓값을 찾는다. 풀이 #1 (Python) 리스트 arr의 초기값으로 0을 넣어두고 S의 각 원소가 홀수면 arr에 0을 추가하고, 짝수면 arr의 마지막 값을 1 증가시킨다. 따라서 arr에는 짝수로 이루어진 수열의 길이가 홀수 원소로 구분되어 저장되고, 연속된 arr 원소들의 합은 그 원소 수만큼 S에서 홀수 원소를 삭제한 짝수로 이루어진 수열의 길이와 같다. arr을 복제해 리스트 dp에 저장하고, for문에서 앞의 홀수 원소를 반복 횟수만큼 삭제한 수열의 길이로 dp를 갱신해 나간다. 같은 for문 내에서 구한 값이 현재 결과에 영향을 미치지 않도록 dp의 원소들을 역순으로 갱신한다. def solution()..