📚 문제 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..
📚 문제 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[..
📚 문제 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net 🔍 아이디어 구현문제로 반례를 잘 생각해야 하는 문제인 것 같다. 방향을 문자로 입력받아서 이 부분을 enum으로 처리했는데 hash 등을 이용하는 방법이 더 빠를 것 같다. 또한, 행과 열의 순서와 이동할때의방향을 고려해서 문제를 풀어야 한다(헷갈린다..) 또한 행은 감소하는 방향으로 1~8까지 있지만 열을 A~H로 [1,8] , [A, H] 범위를 체크해야 한다. 풀이순서. 1. 킹을 움직이고 킹의 이동이 범위를 넘어간 경우 넘어간다. 2. 킹이 움직인 위치가..
