📚 문제 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[..
📚 문제 1063번: 킹 8*8크기의 체스판에 왕이 하나 있다. 킹의 현재 위치가 주어진다. 체스판에서 말의 위치는 다음과 같이 주어진다. 알파벳 하나와 숫자 하나로 이루어져 있는데, 알파벳은 열을 상징하고, 숫자는 www.acmicpc.net 🔍 아이디어 구현문제로 반례를 잘 생각해야 하는 문제인 것 같다. 방향을 문자로 입력받아서 이 부분을 enum으로 처리했는데 hash 등을 이용하는 방법이 더 빠를 것 같다. 또한, 행과 열의 순서와 이동할때의방향을 고려해서 문제를 풀어야 한다(헷갈린다..) 또한 행은 감소하는 방향으로 1~8까지 있지만 열을 A~H로 [1,8] , [A, H] 범위를 체크해야 한다. 풀이순서. 1. 킹을 움직이고 킹의 이동이 범위를 넘어간 경우 넘어간다. 2. 킹이 움직인 위치가..
📚 문제 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 🔍 아이디어 배열의 사이즈가 작아서 그냥 배열로 저장하여 찾는 방법을 선택하였다. 해당문제에서 시간 초과가 나는 포인트는 상어의 속도라고 판단하여 해당 부분을 따로 처리해 주었다. 상어의 방향이 오른쪽 왼쪽인 경우, 위아래인 경우를 따로 처리하였다. 먼저 오른쪽, 아래쪽인 경우는 velocity만큼 더하고 , 왼쪽 위쪽인 경우에는 velocity만큼 뺀다. 만약 위 아..
📚 문제 2758번: 로또 선영이는 매주 엄청난 돈을 로또에 투자한다. 선영이가 하는 로또는 1부터 m까지 숫자 중에 n개의 수를 고르는 로또이다. 이렇게 열심히 로또를 하는데, 아직까지 한 번도 당첨되지 않은 이유는 www.acmicpc.net 🔍 아이디어 처음 문제를 봤을 때는 그냥 dfs를 이용하는 풀이를 생각했다 -> 그래서 3번 시간 초과 났다 (dfs에서도 최적화 가능한 줄 알고 여러 번 도전했다.) 3번이나 시간초과 후에는 dp를 떠올렸다. 생각해보니까 가능하다는 생각이 들었다. 그래서 dp로 수정하고 제출하니까 16%에서 틀렸습니다 라는 메시지가 나와서 당황했다. 뭐지.. 설마 타입문제인가 라는 생각으로 엣지 케이스를 넣으니까 음수로 나와서 오버플로우발생을 확인했다 이후에 long으로 선언..
📚 문제 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 🔍 아이디어 기본적인 구현 문제이다. DFS/ BFS 두 가지로 모두 풀 수 있지만 나는 BFS를 이용해서 풀이하였다. 갈 수 있는 길이 대각선을 포함함으로 경로에 추가한다. 또한 모든 섬을 찾아야 하기에 모든 배열을 탐색하면서 이미 방문하지 않은 섬의 경우에 탐색을 시작하고 해당섬을 BFS로 순회하면서 visit 배열을 색칠하면 된다.(방문처리를 한다) 즉, 모든 지도를 탐색하면서 1번 섬을 만난 경우 1번 섬에 대해 visit을 모두 칠하고, ..
📚 문제 https://www.acmicpc.net/problem/1092 🔍 아이디어 크래인을 효율적으로 사용하는 것이 중요하다고 생각했습니다. 한 크래인이 실을 수 있는 물건들중 가장 무거운 물건을 선택한다면 가장 효율적으로 크래인을 사용하여 모든 화물을 실을 수 있을것이라 판단하여 이분 탐색을 이용하여 크래인이 실을 수 있는 무게 N보다 작은 수중 가장 큰 숫자를 선택했습니다. -1이 나오는 경우는 크래인의 옮길 수 있는 가장 큰 허용량 보다 무거운 화물이 있는경우이기에 sort를 이용하여 정렬후에 비교하였습니다. 이분탐색에서 어떤 한 숫자보다 작은 수중에 가장 큰 수는 아래와 같은 로직으로 해결할 수 있습니다 crane이 실을 수 있는 경우 result를 갱신합니다. //이분탐색은 정렬되어있어야 ..
