www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 아이디어: 조건: X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. dp[i] = min(dp[i-1], dp[i//3], dp[i//2]) #i가 3,2로 나누어 떨어지는 경우.. dp[1]=0, dp[2]=dp[3]=1 n까지 bottom-up 방식으로 반복문을 이용하여 구현하였다. import sys n = int(sys.stdin.readline()) dp = [0]*(1000001) dp[2]=1 dp[3]=1 for i in range(4,n+1): a = i%3..
전체 글
www.acmicpc.net/problem/1757 1757번: 달려달려 어제, 그리고 어제 어제 단체달리기를 두 번이나 하였다. 원장선생님의 이러한 하드 트레이닝으로 월드 학생들의 체력은 거의 박지성 수준이 되었다. 그래서 월드 학생들은 운동장을 도는데 정 www.acmicpc.net 아이디어: DP를 구성하는 방법을 떠올리는 방식이 어렵다. 조건 - 1분을 달리면 지침 지수는 1이 올라간다. 1분을 쉬면 지침 지수는 1 내려간다. -> 지침지수가 0일 때 쉬어도 그대로 0이다. - 쉬기 시작하면 지침지수가 0이 되기 전에는 다시 달릴 수 없다. - 달리기가 끝나면 지침지수는 0이 되어야 한다. -> 마지막 n분째에는 달릴 수 없다. DP[x][y][z] = x초에 y의 지침지수를 가지고 z는 뛰고 있..
www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 아이디어: DP를 활용하여 생각해보면 1, 2, 3으로 나눌 수 있으므로 i 번째 숫자 = i-1번 숫자에서 1을 더한 경우 + i-2번 숫자에서 2를 더한 경우 + i-3번 숫자에서 3을 더한 경우 로 구할 수 있다. 따라서 dp를 만들어서 dp[i] = dp[i-1]+dp[i-2]+dp[i-3] 으로 푼다. 틀린 부분: 앞선 피보나치 문제처럼 재귀함수를 만들어서 풀 수 있지 않을까 하고 구현해보았는데 시간 초과가 났다. #시간초과 import sys sys...
www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 아이디어: DP의 기본 문제 DP의 핵심은 부분 문제로 나누는 것 + Memorization 일반적인 재귀함수로 풀면 이미 계산한 것을 또 다시 계산해야 하는 비효율성 발생 -> 계산한 값을 저장하는 배열을 만들어 활용! import sys n = int(sys.stdin.readline()) dp = [-1 for _ in range(n+1)] def solve(n): if..
www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 아이디어: 열: row = [[False]*10 for _ in range(9)] 행: col = [[False]*10 for _ in range(9)] 3*3: square = [[False]*10 for _ in range(9)] -> 1~9까지 숫자가 있으면 해당 인덱스 True 주어진 스도쿠 행렬을 돌면서 0인 경우 조건을 검사하고 조건에 부합하면 일단 넣기. 어려웠던 부분: 이차 배열 선언을 [[Fal..
www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 아이디어: 사전 순으로 증가하는 순서로 출력해야 하므로 입력으로 주어진 N개의 자연수 정렬. 중복되는 수열을 체크할 방법이 관건. -> 일단 각 숫자가 사용되었는지 여부를 확인하는 isUsed = [N] -> 중복되는 수열인지 체크는 바로 이전에 출력한 수열과 동일한지 체크하면 되지 않을까?(X) -> 테스트 케이스 2번째의 경우처럼 똑같은 원소가 여러 개 있을 경우 중복 체크가 안됨 -> 바로 이전에 선택한..
www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 아이디어: 인덱스 i*j 각 열에 퀸이 하나씩 있어야 한다. for i in (0~N) 1. 같은 행 -> j 2. 오른쪽 위 대각선 -> i+j 3. 오른쪽 아래 대각선 -> i-j+N-1 (인덱스가 음수가 나오면 안되니까) 코드: 파이썬 함수 안에서 변수의 값을 바꾼 후 나와서 출력시킬 때.. 전역변수를 설정해야 한다. global import sys n = int(sys.stdin.readline()) check1 = [..
www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 아이디어: 역시 재귀함수를 이용한다. 오름차순으로 출력하므로 중복을 따로 검사하지 않아도 중복이 보장된다. 코드: import sys n, m = map(int, sys.stdin.readline().split()) ans = [0]*m def solve(level, start): if (level==m): for i in ans: print(i, end=" ") print() return for i in r..
www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 아이디어: 재귀함수 이용. solve(level) -> level == m 이되면 출력하고 return for (1, n+1) 까지 중복 여부를 검사(isused[] 배열을 이용)하고 중복되지 않는 경우 정답 배열에 추가 재귀함수 이용법 숙지 코드: import sys n, m = map(int, sys.stdin.readline().split()) isUsed = [False]*n ans = [0]*m de..
www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 아이디어: N과 M은 8보다 크거나 작고, 50보다 작거나 같은 자연수이므로 8*8의 가능한 모든 경우를 찾고, 각 경우에 칠해야 하는 정사각형의 최소 개수를 모두 구해도 주어진 ㅅ ㅣ간 내에 해결 가능하다.(브루트포스) 8*8 가능한 모든 경우: for (0~N-8)까지 탐색 칠해야 하는 정사각형의 최소 개수: 칠할 수 있는 경우는 W가 i+j=짝수 이고 B는 i+j 홀수인 경우와, W는 홀수, B는 ..