흙금이네 블로그

아이디어 동적 계획법과 DFS로 동전을 더 이동할 수 없는 곳에서부터 이동할 수 있는 최대 횟수를 구해 나간다. 풀이 람다식으로 입력으로 주어지는 문자열에서 H는 0으로, 나머지는 정수형으로 바꾼 리스트를 리스트 board에 저장한다. 각 칸의 동전 최대 이동 횟수를 저장하는 2차원 리스트 dp와 각 칸의 방문 여부를 표시하는 2차원 리스트 visited를 만든다. 가장 왼쪽 위칸의 행, 열, 이동 칸 수를 인자로 함수 dfs를 호출한다. 함수 dfs에서는 현재 칸을 이미 방문하여 최대 이동 횟수가 dp에 저장되어 있으면 해당 값을 반환하여 종료한다. dp에 저장되어 있지 않으면 최대 이동 횟수를 저장하는 move에 1을 저장하고, visited에 방문 표시를 한다. 보드의 범위를 벗어나지 않고 이동할 ..

아이디어 에라토스테네스의 체로 소수를 판정하고, 메모이제이션을 사용하여 시간을 단축한다. 풀이 예전에 작성한 코드가 재채점 후 시간 초과가 되어 다시 풀어본 문제로, 메모이제이션이나 불필요한 과정을 생략하여 실행 시간을 줄여야 했다. 에라토스테네스의 체로 소수인 수의 인덱스는 True, 소수가 아닌 수의 인덱스는 False로 하는 리스트 p를 만든다. 이때 입력으로 주어지는 짝수 정수를 두 홀수 소수의 합으로 나타내면 되므로 홀수이면서 소수가 아닌 수만 확인한다. 따라서 i는 3부터 시작하여 2만큼 건너뛰고, j는 i*3에서 짝수 크기만큼 건너뛰어 홀수 인덱스만 확인하도록 한다. 메모이제이션을 위해 딕셔너리 memo를 만들고, n이 0이 아닐 때까지 while문을 반복한다. n이 memo에 존재하면 그대..

아이디어 동적 계획법으로 각 칸에서 만들 수 있는 정사각형 한 변의 크기를 저장해 나간다. 풀이 #1 리스트 dp에 배열 첫 줄을 입력 받고, 결과값을 저장하는 변수 res에 배열 첫 줄에서 가장 큰 값을 저장한다. for문에서 arr에 배열을 한 줄씩 입력 받고, 차례로 arr에서 1로 된 칸들에 왼쪽 칸, 위쪽 칸, 좌상단 칸 중 최솟값을 더한다. 위쪽 칸과 현재 칸은 각각 다음 칸에서 좌상단 칸과 왼쪽 칸이 되므로 하나라도 0인 경우 두 칸을 건너뛰도록 한다. res를 현재 줄의 최댓값과 비교해 갱신하고, 다음 for문을 위해 dp를 arr로 대체한다. res는 정사각형 한 변의 길이를 나타내므로 마지막에 res를 제곱하여 출력한다. import sys input = sys.stdin.readlin..