[백준][Python][15989][DP] 1,2,3더하기 4
문제 : https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 1+3 (3+1) 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net DP 문제인데 좀 까다롭다. 1,2,3 더하기 시리즈를 보면 하나같이 DP 문제인데, 이문제가 제일 어려웠다. 1,2,3을 써서 숫자를 만드는데, 숫자는 같으면서 순서만 다른건 하나로 하는 것이다. 밑에는..
더보기
[백준][Python][15558][BFS] 점프 게임
문제 : https://www.acmicpc.net/problem/15558 15558번: 점프 게임 첫째 줄에 N과 k가 주어진다. (1 ≤ N, k ≤ 100,000) 둘째 줄에는 왼쪽 줄의 정보가 주어진다. i번째 문자가 0인 경우에는 위험한 칸이고, 1인 경우에는 안전한 칸이다. 셋째 줄에는 오른쪽 줄의 정보가 주어지고, 각 문자의 의미는 왼쪽 줄의 의미와 동일하다. 왼쪽 줄의 1번 칸은 항상 안전한 칸이다. www.acmicpc.net BFS 문제다. 현재 위치를 x, 현재 줄을 line, 현재 시간을 time이라 할 때, 큐에 각각 [(line+1) %2, x + (k, 1, -1), time+1]을 넣어준다. 이때, ( (line+1) %2, x + (k, 1, -1) ) 에 대해 이미 탐색..
더보기
[백준][Python][17822][구현] 원판 돌리기
문제 : https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다. (i, 1)은 (i, 2), (i, M)과 인접하다. (i, M)은 (i, M-1), (i, 1)과 인접하다. (i, j)는 (i, j-1), (i, j www.acmicpc.net 구현 문제다. 우선, clockwise, counterclockwise, allavg, allsum 함수는 아래와 같다...
더보기
