DP
-
[백준] 9655번 돌 게임Algorithm Study/Python 2024. 3. 17. 00:00
https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 풀이 두 사람이 돌을 1개 또는 3개씩 가져가면서 마지막 돌을 가져가는 사람이 이기는 게임이다. 두 사람이 1개 또는 3개의 돌을 가져갈 수 있는 경우는 1/1, 1/3, 3/1, 3/3 이고 서로 무조건 이기기 위한 선택을 하기 때문에 N번째에서 이긴 사람이 N+2, N+4, N+6에서도 모두 이기게 된다. 즉 홀수, 짝수로 나뉘어져 승리하는 인원이 정해진다. DP 기본적인 문제를 다시 풀려고 선택하였지만 단순한 문제가 되어버렸다. 전체 코드 N = int(input()) if N % 2 == 0: print('CY..
-
[백준] 17070번 파이프 옮기기 1Algorithm Study/Python 2021. 5. 1. 04:03
www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의..
-
[프로그래머스] 동적계획법(DP) 01. N으로 표현Algorithm Study/Python 2021. 3. 31. 15:06
programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 문제설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. 제한사항 N은 1 이상 9 이하입니다. number는 1 이상 32,000 이하입니다. 수식에는 괄호와 사..