영호

문제 링크 https://www.acmicpc.net/problem/2170 나의 풀이 가장 핵심 로직은 겹치는 줄 들을 어떻게 합치느냐입니다. 예제 입력 중 (1,3), (2,5), (3,5)는 (1,5)로 합칠 수 있습니다. 합쳐지는 조건 우선 주어진 입력들을 오름차순으로 정렬합니다. 첫 번째 입력 좌표를 start, end변수로 설정합니다. 두 번째 좌표부터 끝까지 탐색하며 합칠 수 있는지 살펴봅니다. 만약 i번 좌표의 시작점이 기존 좌표의 start

문제 링크 https://www.acmicpc.net/problem/14501 나의 풀이 주의점 n + 1일에 퇴사를 하기 때문에 상담이 n+1 일에 끝나는 경우까지 고려해야 합니다. 처음 접근 1일부터 n일까지 해당 날짜의 상담을 진행하는 경우 안하는 경우를 고려해서 점화식을 세우려고 시도해봤습니다. 만약, 1일차 상담에 이틀이 필요할 때 3일차 상담을 진행하는 경우의 점화식을 어떻게 세울지 고민하다 결국 해결하지 못하고 구글링을 했습니다. 구글링 결과 1일 부터 시작하는 것이 마지막 n일부터 시작해서 dp테이블을 갱신합니다. n=7 7일차 상담은 이틀이 필요하기 때문에 7 + 2 > n+1 이므로, 상담을 진행할 수 없습니다. 2일차 상담의 경우 5일이 필요하기 때문에 max(20 + dp[5], d..

문제 링크 https://www.acmicpc.net/problem/5427 나의 풀이 기본적으로 최소시간을 구하는 문제라 BFS를 사용했습니다. 그리고 문제를 '불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다' 라는 문장이 있습니다. 즉, 불이 먼저 동서남북으로 한 칸씩 번지게 한 다음에 상근이가 동서남북으로 움직일 수 있는지 구별해야 합니다. 구현 기능 불은 동서남북으로 한 칸씩 번져야 한다. 단, 벽에는 불이 붙을 수 없다. 상근이도 동서남북으로 한 칸씩 움직일 수 없다. 역시 벽으로는 이동할 수 없고, 불이 붙으려는 칸으로 이동할 수 없다. -> 불을 먼저 번지게 함으로써 구별 상근이가 x,y 좌표 중 하나라도 map의 가장자리에 도착하게 되면 탈출가능한 경우이다. 막혔던 점 sB..

문제 링크 https://www.acmicpc.net/problem/1941 나의 풀이 잘못된 접근 잘못 세운 점화식 $$ dp[i] = dp[i - (가장 큰 제곱근 ^ 2)] + 1$$ 단순하게 가장 큰 제곱근의 제곱을 빼서 dp 테이블을 갱신하는 것이 최솟값이라고 생각을 했습니다. 예를 들어 i = 26의 경우 가장 큰 제곱근인 5의 제곱 25를 26에서 뺀 뒤 나온 1. 즉, dp[26-25] + 1 이 무조건 최솟값이라고 생각했습니다. $$ 26 = 1^2 + 5^2$$ 올바른 접근 점화식의 경우 위에서 세운 점화식이 아예 틀린 것은 아니지만 가장 큰 제곱근만 생각하는 것이 아닌 1 ~ 가장 큰 제곱근의 경우를 모두 생각해야 합니다. 12를 시도해보면 좋을 거 같습니다. $$ dp[i] = m..

문제 링크 https://www.acmicpc.net/problem/9465 나의 풀이 우선, 3xn 크기의 dp테이블과 2xn 크기의 stickers배열을 생성합니다. dp[0][n] stickers[0][n]의 스티커를 뜯었을 때의 최댓값을 저장하고, 두 번째 행도 이와 마찬가지입니다. dp[2][n]은 stickers[0][n], stickers[1][n] 모두 뜯지 않았을 때의 최댓값을 저장합니다. 스티커를 뜯는 방식으로 3가지를 고려할 수 있습니다. 0행의 n열 스티커를 뜯는 경우 -> stickers[0][n]을 뜯는 경우 stickers[0][n]을 뜯은 경우 이와 인접한 stickers[0][n-1] 스티커는 뜯을 수 없기 때문에, stickers[0][n-1] 스티커를 뜯지 않은 경우인..

문제 링크 https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 나의 풀이 x번 카드와 y번 카드를 골라 그 두 장에 쓰인 수를 더한 값을 계산한다. (x ≠ y) 저는 처음에 x!= y의 뜻이 x, y가 같은 수면 안된다는 뜻인 줄 알았는데, 그게 아니라 같은 위치의 카드를 고를 수 없다는 뜻입니다. heapq를 사용하여 풀이했습니다. Code import heapq cards_num, m = map(int,i..

문제 링크 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 나의 풀이 최단거리를 구하기 위해 bfs를 사용했습니다. 최대 입력이 100,000까지라 maps를 100,001 크기로 설정했습니다. bfs알고리즘을 수행하며 x+1, x-1, x*2로 탐색을 했습니다. 인덱스 에러 방지 및 방문한 지점에 대해서 예외처리를 진행합니다. deque.leftpop()에서 목표 지점과 동일한 값이 나오면 bfs()를 종료합니다...

문제 링크 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 나의 풀이 이 문제는 구글링을 통해 풀이 방법을 참조했습니다. 각 알파벳들이 단어의 어느 자릿수에 위치하는지 확인하고 이를 딕셔너리에 저장합니다. ex) 'ADC'이면 A는 100, D는 10, C는 1을 딕셔너리에 'A' = 100, 'D' = 10, 'C' = 1로 저장하고, 다른 단어들에 대해서도 똑같이 각 자릿수를 딕셔너리에 더해줍니다. 알파벳들이 어느 자릿수에 위치하는지..