https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net # 각 좌표마다 경우의 수가 3가지이므로(가로, 세로, 대각선) 3차원 배열을 사용하였다. # 처음 파이프는 (0, 0), (0, 1)에 가로로 놓여있으므로 dp[0][1][0]에 1을 넣어준다. -> (0, 1)에 파이프 끝이 있고, 가로로 놓여있다는 뜻이다. (dp[x][y][0] = (x, y)에 파이프 끝이 있고, 가로로 놓여있다는 뜻 dp[x][y][1] = (x..
https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net # 일단.. 노트나 종이에 손으로 하나하나 경우의 수를 세면서 따져본다. (그러면서 규칙이 발견되길 기도한다.) 보통 DP문제는 앞에서부터 하나하나 세거나, 뒤에서부터 하나하나 세다보면 규칙이 보이는 경우가 많다. # dp[N][K]를 K개의 수로 N을 만드는 방법이라고 하자. dp[0][1] = 1, dp[1][1] = 1... dp[N][1]은 1개의 수로 N을 만드는 방법이므로 무조건 1이다. 또한, dp[0][K] 역시 K개의 수로 0을 만들어야 하므로 0만 더해야한다. -> dp[0][K]도 무조건 1이다. # 이..
https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net # DP문제이다. 1. 우선 게임판 m을 입력받고 dp테이블도 m과 같은 크기로 선언해준다. 2. (0,0)부터 한 칸씩 이동하며 m[i][j]가 0이면 continue하고, 아니면 점프를 뛸 수 있는지 판단한다. (11, 13줄) 3. 점프를 뛸 수 있으면, 점프를 뛴 곳의 dp값의 현재 좌표의 dp값을 더해준다. 4. 맨 오른쪽 아래인 dp[-1][-1]을 출력한다. import s..
https://www.acmicpc.net/problem/2002 2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net # 터널에 들어가는 차량을 입력받아 enter 딕셔너리에 {'car': i}로 저장한다. (car는 입력받은 차량이름, i는 순서를 나타내는 index) # 터널에서 나오는 차량들을 out이라는 배열에 저장한다. # 나오는 차량들을 처음부터 확인하며 현재 차량의 인덱스(들어간 순서)가 뒤에 나오는 차량들의 인덱스보다 큰 경우가 하나라도 존재한다면 추월한 것이므로 answer 1증가..
https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net # 스택문제이다. https://www.acmicpc.net/problem/9935 BOJ 9935번: 문자열 폭발과 같은 알고리즘으로 풀면된다. # 문자열 s를 입력받고 s의 첫문자부터 stack에 넣는다. 넣는 과정에서 stack[-1]이 'P'이고 현재 스택의 마지막 4개의 원소가 'PPAP'이면 del stack[-4: ]를 통해 'PPAP'를 날려주고 'P'를 stack에 넣어주는 것을 반복한다. # 모든 과정이 끝난뒤 stack에 'PP..
https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 첫째 줄에 자연수 N(1≤N≤1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 편의상 0은 적혀있지 않다고 가정하자. www.acmicpc.net # deque를 사용해서 풀어야 하는 문제이다. 1. 풍선안에 있는 숫자들을 s로 입력받고 인덱스와 함께 dq에 저장한다. s = [3, 2, 1, -3, -1]이면, dq = [[1, 3], [2, 2], [3, 1], [4, -3], [5, -1]]이 된다. 2. dq에 원소가 존재하는 동안 반복문을 돌며 dq의 첫번째 원소를 pop해서 answer에 index를 넣어준다. dq의 하나의 원소만 남았다면, 그 원소의 인덱스..
https://www.acmicpc.net/problem/2841 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수 www.acmicpc.net # 스택문제이다. 1. 우선 줄이 6개이므로 st에 빈 배열 6개를 선언해준다. 2. N만큼 반복문을 돌며 줄 번호와 프렛번호를 입력받는다. 3. 만약 st[line-1]에 원소가 존재한다면, 이미 그 줄을 누르고 있는 상태이다. 따라서 p(프렛번호)와 그 줄에서 가장 높은 음인 st[line-1][-1]을 비교해서 p가 더 작으면 그 줄에 있는 높은 음을 ..
https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net # stack문제이다. # 처음에 모든 인원들을 모두 stack에 넣고 풀어봤는데, 중간중간 필요할때 stack에 넣고 바로 빼는 상황이 필요해서 다시 풀었다. 1. idx가 N이 될때까지 반복문을 돌며 만약 stack안에 원소가 존재하고 stack[-1]이 end(간식 받아야 할 사람)이면 end를 1증가 시켜주고 stack.pop()을 해준다. stack[-1]이 end가 아니면 studen..
모르는 사이에 조금씩 조금씩..
