코린이 탈출기

문제 바로가기 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net Algorithm Dynamic Programming Logic 스티커를 고르는 경우는 i번째 위치에서 위를 선택/아래를 선택/고르지 않기 세 가지 경우이다. 그 전에 위에 있는 스티커를 골랐다면, 현재 위치에서도 위의 스티커는 고를 수 없다. 그 전에 아래에 있는 스티커를 골랐다면, 현재 위치에서도 아래의 스티커는 고를 수 없다. 이렇게 불가능한 경우에 유의하면서 코드를 작성하면 된다. *핵심코드 for i in range(1, n+1..

문제 바로가기 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 1. DP 풀이법 현재 num과 이전의 값들의 비교하는데, 이전 값보다 현재값이 크다면 그 dp배열의 현재 값과, dp배열의 이전 값 + 1 중 더 큰 값으로 갱신한다. dp의 최댓값이 답이다. N = int(input()) number = [int(x) for x in input().split()] dp = [1] * N for i in range(N): for j in range(i): if number[j] < number[i]: dp[i] =..

Algorithm 순열, 시뮬레이션 Logic 주사위를 10번 던지는데, 각 주사위마다 어떤 말을 옮길지 결정해야하므로, 중복순열을 만들었다. -> 개수: (말 개수 = 4)^10개 diceMap: 각 노드에서 연결된 다음 노드번호를 저장하는 adj 리스트 diceScore: 각 노드에 해당하는 포인트를 저장하는 리스트 visited: 말들이 위치한 곳을 나타내는 리스트 makePermutation(now, goal, arr): 중복 순열을 만드는 함수 하나의 중복순열이 완성되면 getScore함수를 통해 그 경우에 얻는 score을 반환받는다. getScore(arr, diceInfo) arr: 각 주사위를 던질 때마다 옮길 말의 정보가 담긴 리스트 diceInfo: 현재 0~3번 말이 있는 위치를 저..

Algorithm 구현, 시뮬레이션 Logic 풀이 순서 상어가 처음 위치한 좌표로 sharkInfo와 sharkScent를 초기화한다. 시간을 늘려가면서 다음을 수행한다. sharkInfo에 들어있는 상어들을 하나씩 이동시킨다. 이동 rule 아무 냄새 없는 칸 찾기 -> 그런 칸이 여러개라면 우선순위를 따른다. 자신의 냄새가 있는 칸 찾기 -> 그런 칸이 여러개라면 우선순위를 따른다. 같은 위치에 여러 상어가 위치한다면, 가장 작은 번호의 상어를 제외하고 모두 없애준다. 현재 scentMap에 냄새가 남아있다면, 이 냄새가 남아있을 시간을 -1한다. (시간이 흐름을 의미) sharkInfo를 보면서 상어가 옮겨간 위치에 sharkScent를 업데이트한다. 시간이 1000초를 초과하면 -1을 출력한다...

Algorithm 시뮬레이션, 구현 Logic 접근법 -> green map을 blue map 처럼 만들어서 따로 구현하지 않고 한꺼번에 한다 ! 모노미노도미노 map은 이러한 모양을 가지는데, 이 때 우리가 필요한 정보는 초록색 map과 파란색 map이다. 빨간색 map은 y, x만 알면 되기 때문에 굳이 배열로 만들지 않아도 된다. 대부분의 풀이가 greenMap과 blueMap 각각을 따로 구현했던데, 나는 greenMap을 blueMap 모양으로 만들어서 함수 하나로 다 풀 수 있도록 했다. 이 때 주의할 점: redMap의 행 기준으로 blueMap 블럭을 민다 redMap의 열 기준으로 greenMap 블럭을 민다 기본적으로 새로운 블럭을 놓을 위치를 찾는 구현은 blueMap 기준으로 했고,..

Algorithm 시뮬레이션 Logic zoneInfo: 칸의 정보를 담음 -> Map의 크기를 (N+2) * (N+2) 로 늘려서 바깥 부분은 파란색 구역으로 만든다. chessMap: 체스 list를 원소로 갖는 2차원 Map (한 구역에 체스말이 여러개인 경우, 밑에 위치하는 체스 index가 더 작음- stack 구조) chessInfo: 체스말의 좌표를 저장하는 리스트 -> 이 리스트를 사용하면 2차원 순회할 필요가 없어진다 moveChess(): 체스 번호를 순회하면서 해당 번호의 체스를 움직이는 함수 체스 번호가 위치한 Map에서 그 번호를 만날 때까지 원소들 pop해서 newList의 앞부분에 insert한다. updateMap(now_y, now_x, False, newList, targ..

문제 바로가기 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net Logic Algorithm: 시뮬레이션, BFS findDistance(taxi_y, taxi_x, passengerMap): BFS로 현재 택시 위치에서 승객의 위치까지의 그 승객의 index와 최소 거리를 return 하는 함수. 만약 최소 거리가 여러 개라면, 여러 개 모두 return passengerMap: 현재 승객들의 위치의 좌표를 저장하는 이차원 리스트(택시 탑승 완료된 승객은 표시 x) que..

www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net Logic erase_set: 원판에서 지울 좌표를 저장하는 Set -> 중복 제거를 위해서! checkHorizontal(num): 원판의 가로라인에서 인접하면서 수가 같은 경우를 찾아서 erase_set에 저장한다. checkVertical(num): 원판의 세로라인에서 인접하면서 수가 같은 경우를 찾아서 erase_set에 저장한다. processAverage(): 원판 점수의 평균을 구하..