여름의 서재

📕 문제 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 💡 풀이법 1. 먼저 구름의 첫 위치의 좌표들을 clouds라는 deque에 담는다. 2. clouds를 돌면서 구름을 이동시킨 값을 다시 clouds에 넣는다. 이동시킨 자리에 위치한 칸의 물의 양을 1씩 증가 시켜준다. (이와 동시에 모두 0으로 채워진 N x N 의 격자 칸 is_clouds를 만들어서 구름이 있는 칸은 1로 바꿔준다. 3. 그 다음 다시 clouds를 돌면서..

📕 문제 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 💡 풀이법 1. dice의 각 6개 방향의 번호를 길이가 6인 리스트로 표현한다. (나는 0번 인덱스의 번호가 지도와 닿아있는 방향) 2. 동, 서, 남, 북으로 돌릴 때, 각 방향의 번호들을 바꿔준다. 3. 주사위를 놓는 곳이 0이라면 0번 인덱스의 숫자를 지도의 닿아있는 부분에 넣고, 반대로 0번 인덱스가 0이라면 지도..

📕 문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 💡 풀이법 : 빨간 구슬을 구멍에서 빼낼 수 있는지 최소한의 동작 횟수를 구해야 하기 때문에 bfs를 이용했다. 1. 빨간 구슬과 파란 구슬이 두개 다 움직여야 하기 때문에 두개의 deque를 만든다. (이때, deque에 들어가는 원소는 (x의 좌표, y의 좌표, 현재까지의 동작 횟수) 이다.) 2. while문을 돌면서 구슬을 각자의 ..

📕 문제 https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 💡 풀이법 1. 학생을 키로 하고 학생이 선호하는 학생의 리스트를 value로 하는 like 딕셔너리를 만들었다. 2. 학생들을 위치시킬 N*N의 2차 행렬 room을 만들었다. 3. 각 학생마다 교실을 돌면서 각 자리의 행과 열, 주변의 좋아하는 사람 수, 빈 자리 수 를 구해서 priority리스트에 넣는다. 4. 모든 자리를 다 돌고 난 후 priority를 정렬해서 가장..

📕 문제 https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 💡 풀이법 : 문제를 이해하지 못해 한참을 해맸다..;; 이해하는데 시간이 더 걸린 문제ㅋㅋㅋㅋ 1. 컨베이어 벨트를 길이가 2N인 deque로 만들어주고, 칸마다 박스가 있는지 없는지를 체크하는 boxes 리스트도 deque로 만들어 준다. 이때, 박스는 컨베이어 벨트의 위에만 있을거기 때문에 아래칸은 무시하고 길이가 N인 리스트를 만들었다. 2. 이제 문제에 나온..

📕 문제 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 💡 풀이법 1. 최대값을 저장해줄 max_dp, 최소값을 저장해줄 min_dp를 만든다. (이때, 일반적인 dp와 다르게 n개의 길이로 만들어주면 메모리 초과 에러가 난다..ㅜ) 2. 당장 왼쪽, 가운데, 오른쪽에서 어떤 값이 최대, 최소일지 알 수 없기 때문에 각 위치를 선택했을때의 최대, 최소값을 구해주어야 한다. 3. 처음에는 0행의 숫자들을 넣어준다. 4. N개의 행이 있기 때문에 for문을 N..

📕 문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 💡 풀이법 1. 연산자의 개수를 받아서 연산자의 개수만큼 연산자를 만들어서 연산자 리스트(opp)에 담아준다. (0: 덧셈, 1: 뺼셈, 2: 곱셈, 3: 나눗셈) 2. 나올수 있는 순서의 경우의 수를 permutation으로 만들어준다. (단, 중복이 나올수 있기 떄문에 set을 해준다. 예를 들어, 0,1,1,2,3 이면 1이 두..

📕 문제 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 💡 풀이법 1. 전화번호의 정보를 먼저 모두 리스트에 담아주었다. 2. 각 전화번호 중에 접두사가 비슷한 것끼리 비교를 해주어야 하기 때문에 sort 함수를 이용해서 정렬을 해주었다. 3. 문자열들을 정렬해주게 되면 사전순으로 정렬이 된다. '9111', '911', '921'이라는 문자열 세 개가 있다면 '911', '9111', '921' 이렇게 정렬이 된다. ..