흙금이네 블로그

아이디어 DFS과 백트래킹으로 남은 포지션에 선수들을 채워 나가며 능력치 합의 최댓값을 찾는다. 풀이 #1 (Python) 각각의 테스트 케이스에 대해 선수들의 능력치를 리스트 S에 입력 받는다. 메모리 절약과 DFS에서 빠른 접근을 위해 능력치가 0이 아닌 선수들만 인덱스와 능력치를 추가해 나간다. 포지션 할당 표시를 위해 0으로 채워진 리스트 visited를 생성하고 함수 dfs를 호출한다. 함수 dfs에서는 차례로 i 번째 선수를 적합한 포지션 중 남은 포지션에 배치하여 할당 표시 후, 현재 선수의 능력치 a를 능력치 합 total에 더하여 다음 선수로 함수를 재귀 호출한다. 배치가 끝나면 결과값 res와 능력치 합 total을 비교해 결과값을 능력치 합의 최댓값으로 갱신해 나간다. import s..

아이디어 부분 문자열들의 팰린드롬 여부를 확인하고 동적 계획법으로 분할 최소 개수를 구해 나간다. 풀이 #1 S의 길이를 N에 저장하고, S의 부분 문자열이 팰린드롬인지 여부를 저장하기 위한 2차원 리스트 is_pal을 만든다. is_pal[i][j]는 문자열 S의 인덱스 i부터 인덱스 j까지의 부분 문자열이 팰린드롬이면 1, 그렇지 않으면 0을 나타낸다. 팰린드롬 분할 최소 개수를 저장하기 위해 0으로 채워진 N+1 길이의 리스트 dp를 만든다. 이후 코드상 인덱스 에러 방지를 위해 문자열 S에서 인덱스 j까지의 팰린드롬 분할 최소 개수는 dp[j+1]에 저장한다. for문은 1부터 시작하므로 is_pal[0][0]과 dp[1]은 for문 실행 전에 저장한다. 길이가 1인 부분 문자열과 바로 앞의 문자..

아이디어 DFS로 넴모들을 격자판에 배치하고 2×2 사각형 칸에 모두 넴모가 배치된 경우는 더 탐색하지 않는다. 풀이 #1 (Python) N이나 M이 1인 경우 2×2 사각형 칸이 존재할 수 없으므로 격자판에서 넴모를 배치하는 모든 경우의 수를 출력한다. 그렇지 않으면 넴모 배치를 위한 2차원 리스트 visited를 만드는데, 인덱스 에러 방지를 위해 행과 열 크기를 1씩 늘린다. (1, 1)을 시작점으로 하여 방문 표시 후 함수 dfs를 호출하고, 시작점 방문 표시를 지우고 다시 함수 dfs를 호출한다. 함수 dfs에서는 현재 칸을 기준으로 현재 칸, 위쪽 칸, 왼쪽 칸, 좌상단 칸에 모두 넴모가 배치되면 백트래킹으로 종료한다. 격자판 한 행씩 왼쪽에서 오른쪽으로 넴모들을 배치해 나가고, 종료 없이 ..