2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제풀이 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 전형적인 DP문제이다. 먼저 DP배열을 2차원 배열로 초기화해서 선언하고 그 안을 점화식으로 채워넣는 방식의 논리를 사용했다. 1. K가 1일때는 수 하나로 N을 표시해야하므로 경우의 수는 반드시 1개이다. 2. N이 1일때는 K-1개의 0과 1개의 1이 필요하므로 경우의 수는 K의 증가율과 같이 증가한다. 3. 여기서 예시를 직접 쓰다가 점화식을 찾았다. 점화식 : dp[i][j] = dp[i-1][j] + dp[i][j-1] 개념적으로 생각했을때 당연하게도 다음수까지의 경우의 수를 구하려면 이전 수까지..

2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제풀이 경우의 수 문제이며 메모리 제한과 시간 제한을 따져봤을 때 DP를 사용해서 풀어야함을 알 수 있었다. k원을 만들기 위해 1

11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제풀이 n의 범위는 1 = 3: dp[2] = dp[1] + 1 for i in range(3, n): dp[i] = dp[i - 1] + dp[i - 2] print(dp[-1] % div) solve()

과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/2579" data-og-url="https://www.acmicpc.net/problem/2579" data-og-image="https://scrap.kakaocdn.net/dn/cFezLf/hyU2tSZnOh/waRUJkQXiM6NkDnkZcjGOK/img.png?width=2834&height=1480&face=0_0_2834_1480,https://scrap.kakaocdn.net/dn/bVfUC0/hyU2tSZnLT/XIkAt4sQ9OkLY7yFBGRwvK..

17298번: 오큰수첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.www.acmicpc.net문제풀이스택을 이용해서 풀었다. N의 최대값이 1,000,000이기 때문에 O(N^2)으로는 절대 풀 수 없었기에 배열을 순회하는 것은 불가능하다고 생각했다. 그래서 오큰수 배열인 NGE배열을 [-1]로 N의 크기만큼 초기화 시켜놓은 후, 어차피 NGE배열의 크기와 입력받은 배열의 크기가 같기때문에 값의 비교를 통해 값과 인덱스를 스택에 저장시켜 NGE배열에 넣어주는 과정을 거쳤다.1. N과 arr을 입력받고 NGE배열을 -1로 N의 크기만큼 초기화시키고 stack을 빈 리스트로..

3190번: 뱀'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임www.acmicpc.net문제풀이이 문제는 근본적으로 뱀이 움직일때마다 움직인 뱀의 머리를 큐에 저장하고 뱀의 꼬리를 큐에서 pop하는 문제이다.자세하게는 맵에 놓인 사과를 먹으면 꼬리를 pop하지 않고 사과를 먹지 못하면 pop한다. 그러다가 뱀이 자기자신의 몸과 닿거나 맵을 나가는경우 종료시킨다.이 문제를 풀면서 유의해야했던 점은 뱀의 방향설정과 사과가 먹혔다면 먹힌 사과를 삭제해야하는 부분이었다.맵에서 사과를 삭제해야하는 개념은 문제의 예제에서 확인할 수 없어 스스로 검증해야한다.1. 먼저 입..

5430번: AC각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.www.acmicpc.net문제선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.배..

2449번: 전구 입력의 첫 번째 줄에는 전구의 수를 나타내는 양의 정수 N과 전구가 표현할 수 있는 색의 수 K가 주어진다. 단, N은 1이상 200이하의 정수이며, K는 1이상 20이하의 정수이다. 두 번째 줄에는 N개 전 www.acmicpc.net 문제 최대 K가지의 서로 다른 색을 표현할 수 있는 전구들이 있다. 이 전구 N개를 다음의 그림과 같이 한 줄로 배치하여 서로 연결한다. (동그라미 안의 숫자는 전구의 색을 의미한다) 각 전구는 스위치가 있어서 전구의 색을 임의의 색으로 바꿀 수 있다. 하나의 전구 색을 바꾸는 경우에는, 색이 바뀌는 전구에 인접한 전구가 같은 색이면, 이 전구의 색도 같이 바뀌게 되며 인접한 전구가 다른 색이 나올 때까지 계속 바뀌게 된다. 예를 들어, 위의 그림에서 ..

3977번: 축구 전술World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역www.acmicpc.net문제World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역으로 나누고, 어떤 선수가 A구역에서 B구역으로 이동하게 하는 움직임을 (A, B)로 표현한다. 모든 도현이의 팀 선수들이 이 움직임만을 따라서 이동한다면 승리하리라고 도현이는 확신한다.도현이는 선수들에게 자신의 전술을 말해주며, 다른 모든 ..

7682번: 틱택토틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고www.acmicpc.net문제틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 두 번째 사람이 O를 놓는다. 어느 때든지 한 사람의 말이 가로, 세로, 대각선 방향으로 3칸을 잇는 데 성공하면 게임은 즉시 끝난다. 게임판이 가득 차도 게임은 끝난다.게임판의 상태가 주어지면, 그 상태가 틱택토 게임에서 발생할 수 있는 최종 상태인지를 판별하시오..