qwlake's Blog

어서오세요, 반갑습니다 :)

백준 1149번 - RGB거리

https://www.acmicpc.net/problem/1149 크게 보면 [이전까지의 집들을 칠하는 최소 비용 + 현재 집을 칠하는 비용] 중에서 최소값을 선택해 나가면 된다. 이웃하는 집(현재 위치의 집에서 이전 집과 다음 집) 끼리는 같은 색을 사용할 수 없으니, [이전까지의 집들을 칠하는 최소 비용 + 현재 집을 칠하는 비용]의 경우는 ...

Posted by qwlake on March 6, 2020

백준 9663번 - N-Queen

https://www.acmicpc.net/problem/9663 일단 퀸은 대각선, 상하좌우 모두 움직일 수 있으므로, 퀸을 배치할때 배치할 퀸 주변 8방향에는 다른 퀸이 없어야 한다. 이 전제를 베이스로 백트래킹을 하다 보면 퀸을 배치할 수 있는 모든 경우의 수가 나온다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ...

Posted by qwlake on March 5, 2020

백준 9251번 - LCS

https://www.acmicpc.net/problem/9251 최장 공통 부분 수열(LCS)문제다. DFS를 써서 해봤는데 시간이 너무 오래 걸린다. DP를 쓰는 것이 가장 무난하다. 행에는 첫 번쨰 입력 문자들을 배치하고, 열에는 두 번째 입력 문자들을 배치하여, 행과 열이 같은 문자라면 이전 상태에서의 최대값에 +1을 해준 값이 현재 ...

Posted by qwlake on March 4, 2020

백준 9095번 - 1,2,3 더하기

https://www.acmicpc.net/problem/9095 전형적인 DP 문제다. 0부터 높여가면서 이전에 거쳐온 숫자들 중에서 가장 많은 경우의 수를 고르고, 해당 숫자에 1을 증가시켜서 DP 배열에 저장한다. 얼핏 보면 피보나치와도 비슷하다. 1 2 3 4 5 6 7 8 9 10 11 T = int(input()) n_list = [...

Posted by qwlake on March 3, 2020

백준 1463번 - 1로 만들기

https://www.acmicpc.net/problem/1463 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟...

Posted by qwlake on March 2, 2020