📚 문제 1189번: 컴백홈 첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다 www.acmicpc.net 🔍 아이디어 해당 문제에서 확인할 점은 왼쪽 아래에서 오른쪽 위로 향한다는 점입니다. 이 부분만 주의해서 DFS 알고리즘을 수행하면 됩니다. DFS알고리즘을 선택한 이유는 K번째 시간에 (0, c-1) 지점에 오는 것이므로 경우의 수를 세기 좋은 깊이 우선탐색을 이용하여 문제를 해결하였습니다. (BFS로 풀면 최단 거리를 구하기는 용이하지만 각 경로에 대해서 해당 경로에 따른 방문탐색을 비교하고 k번째 인 것을 확..
📚 문제 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 🔍 아이디어 그리디 알고리즘으로 해결하였습니다. 해당 문제는 과제의 마감일과 과제의 점수를 주고 최대 얻을 수 있는 과제 점수를 찾는 문제입니다. 저의 경우는 보통의 그리디와 같은 문제인줄 알고 먼저 배열을 마감일을 기준으로 오름 차순 정렬하였습니다. 그 이후에 마감일을 돌면서 해당 마감일 안에 해결할 수 있는 과제들이 있는 경우 우선순위 큐에 넣고 큐에 값이 있는 경우 해당 날자에 해결 할 수 있는 문제가 있는 것임으로 점수가 가장 큰 것을 리턴하도록 하였습니다. 하지만 예제 출력 값과 달라 문제..
📚 문제 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 🔍 아이디어 https://mathbang.net/101#gsc.tab=0 두 원의 위치관계, 내접, 외접 위치관계 또 나오네요. 이번에는 두 원의 위치관계에요. 위치관계 마지막이니까 정신 바짝 차리고 따라오세요. 원과 직선의 위치관계, 원의 할선과 접선, 접점에서 했던 것처럼 두 원이 어떤 관 mathbang.net 내접과 외접에 관한 문제입니다. 각 점을 기준으로 r 떨어진 거리에 사람이 있는경우는 원을 그려서 해당 해당 호 안에 사람이 있어야 한다는 소리로 인식했습니다. 따라서 두 원의 내접과, 외접..
📚 문제 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 🔍 아이디어 단순한 위상정렬 문제입니다. 위상정렬 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예 ko.wikipedia.org 과거에 다른 블로그에 작성한 글입니다. 위상정렬 Topology Sort, 백준 1766 문제집(Java) 위상 정렬(Topology Sort) 정렬..
📚 문제 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 🔍 아이디어 오랜만에 풀어본 위상정렬 문제였습니다. https://lahezy.tistory.com/40 (제가 과거에 작성한 위상정렬 관련 글입니다) 위상정렬 Topology Sort, 백준 1766 문제집(Java) 위상 정렬(Topology Sort) 정렬 알고리즘의 일종으로, 순서가 있는 작업을 차례대로 수행해야 하는 경우 사용할 수 있는 알고리즘이다. 방향 그래프로의 모든 그래프를 방향을 거스르지 않도록 순서 la..
📚 문제 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 🔍 아이디어 해당 문제는 문제를 이해하는데 시간이 조금 걸렸습니다. 간추려서 말하면 각 숫자의 개수를 세고 i 번째 숫자의 오른쪽에 arr내의 i가 있는 숫자보다 더 많은 숫자를 가지고 있는 숫자를 출력하면 됩니다. arr : 입력 숫자 배열 dp(numCnt) : 각 숫자의 개수 stack -> int[3] = {인덱스, 해당 인덱스의 숫자, arr 내의 해당 숫자의 개수) //아래 풀이에서는 [2]번째 것을 생략했습니다. ans : 결과 스택에 들어오는 값의 개수..
📚 문제 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 🔍 아이디어 처음에는 a, b를 비교해서 lcs 문자열을 구하고 c와 비교하는 형식으로 구했더니 틀렸다. 해당 방법은 최대 값을 기준으로 하기 때문에 abc 모두에 대해서 최댓값으로 확신할 수 없다. 예를 들어(반례) a: abcdeqfpk b: qfpkabcde c: qpk 와 같은 경우 a,b에 대해서 bcdef이지만 abc전체에 대해서는 qpk이다. 따라서 abc에 대해서 항상 최장 공통 문자열이 아닌 것이다. 따라서 abc모두에 대해서 3차원 배열로 계산해야 ..
📚 문제 https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 🔍 아이디어 사이클 생성 시에 그래프가 아니다. 1. BFS/ DFS로 탐색 연결된 노드를 탐색한다, 만약 방문했던 노드를 재방문 시에는 사이클 이므로 트리 개수에서 제외한다(-1), 다른 경우는 탐색 시작 시점의 노드에서 (+1) 2. Union Find 정점이 들어오면 두 정점의 부모정정을 찾고 union한다. 만약 부모정점이 동일하면 사이클인 경우이다. 따라서 부모..
📚 문제 https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 🔍 아이디어 지정된 움직임 안에서 최대 몇 개의 사과를 먹을 수 있는가에 대한 문제이다. 0번 움직이면 1번칸, 1번 움직이면 2번칸, 2번 움직이면 1번칸, 즉 칸의 움직임에 따라 그 사람이 있는 위치가 정해진다. 따라서 이것을 이용하여 풀이하였다. 1-1) 먼저 0번 움직인 경우: 예외 처리를 적용해서 이전칸의 값을 받아오고 if (j == 0) score[i][j] = score[i - 1]..
📚 문제 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 🔍 아이디어 먼저 한번 모든 입력을 받는다. 그 후에는 맨 뒤에서부터 i번째의 숫자가 i+1보다 적어도 1이상 작아야 한다는 조건으로 문제를 해결한다. 즉 arr[i] = arr[i+1]-1이어야 한다. 1) 현재 arr[i] 숫자가 arr [ i+1]보다 크거나 같은 경우 (arr[i]>=arr[i+1]) : arr [i] = arr[i+1]-1이어야 최소조건을 만족하기 때문에 sum에 arr[i]-arr[i+1]+1을 더하고 before을 arr[..
