메이쁘

https://www.acmicpc.net/problem/21317 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net 안녕하세요. 이 문제는 간단합니다. DFS를 사용하여 1) 작은 점프(1칸 이동) 2) 큰 점프(2칸 이동) 3) 매우 큰 점프(3칸 이동) -> 1번만 사용 가능 각각의 경우에 DFS로 재귀호출하면 됩니다. 그래서 각 돌에서 작은점프, 큰점프하는 데 드는 에너지를 2차원 배열[n][2]로 저장해두고 (0: 작은점프 / 1: 큰점프) DP 2차원배열[n][2]을 별도로 만들어 해당 돌에 도착했을 때의 에너지 최소 값을 저장해둡니다. (0: K점프 안한경우 / 1: K점프 한경우) DP 초기값(0)인 경우만 구분해서 잘 넣어..

https://www.acmicpc.net/problem/19949 19949번: 영재의 시험 컴퓨터공학과 학생인 영재는 이번 학기에 알고리즘 수업을 수강한다. 평소에 자신의 실력을 맹신한 영재는 시험 전날까지 공부를 하지 않았다. 당연하게도 문제를 하나도 풀지 못하였지만 다행 www.acmicpc.net 안녕하세요 이 문제는 실버3 문제입니다. 총 5^10 경우의 수가 존재하기 때문에, 시간제한인 1초 내에 가능하므로 백트래킹을 활용했습니다. 이 때, 문제에서 적혀있듯이 i번째 문제 정답을 적을 때, i-1번째와 i-2번째 적었던 정답이 같으면 i번째 정답은 절대 i-1번째 정답과 같으면 안됩니다. 이를 위해 i >=2 인 경우, i-1, i-2번째 정답을 확인하고 같을 때 해당 정답을 제외하고 백트래..

https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 안녕하세요. 이 문제는 백준의 회의실 배정, 택배 문제와 유사한 그리디 알고리즘 문제입니다. https://maivve.tistory.com/36 (JAVA) 백준 8980번 : 택배 https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이..

https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 이 문제의 핵심은 위에서 칠한 부분입니다. 각 방에서 상하좌우로 이동이 가능한데, 중요한 것은 불이 켜져있는 방으로만 들어갈 수 있다는 것. 그리고 문제에서 원하는 값은 불을 켤 수 있는 방의 최대 개수입니다. 즉, 최대한 많이 이동하여 방을 방문해서 불을 많이 켜야합니다. 유의사항은 1) 시작점은 무조건 불이 켜져있다. 개수 + 1 2) 방문..

https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 이 문제에서 가장 중요한 부분은 "트리" 구조 인 것 같습니다. 트리를 위해 클래스를 만들고, 이를 1차원 배열로 만든 Graph를 활용한다면, 기존 2차원배열(또는 ArrayList[] 배열) 을 활용한 Graph보다 훨씬 시간과 메모리를 줄일 수 있습니다. 물론, 2차원 int배열은 말할것도 없구요. *** (Edge와 vertex 개수만큼만 만드는 것이 아닌 모든 경우의 수를 그래프로 ..

https://www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 코테에서 알지만 시간 상 풀지 못했었기 때문에 열받아서 관련 문제를 찾아 풀었습니다. 두 가지 방법으로 했는데요. 1) direction(방향) 변수를 별도로 두고, 벽에 닿거나 이미 지나온경우(값이 할당되어있는 경우) 해당 변수값을 변경시켜 방향을 바꿔가며 이동한는 방법 2) (0,0) 부터 시작해서 하좌상우 순서대로 특정 길이만큼 for문으로 이동하는 방법 1) 로 했는데 효율성이 낮아서 2)로..

https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 안녕하세요. 그리디 알고리즘과 우선순위 큐를 활용해 해결했습니다. 처음에 데드라인 이란 단어의 정의가 헷갈려 풀이 방향을 잘못잡았었습니다. 풀고자 하는 문제를 포함하여 이전까지 풀었던 개수가 해당 문제의 데드라인보다 같거나 작아야합니다. 즉, 1) 데드라인이 작을 수록 2) 데드라인이 같을 때 획득할 수 있는 컵라면의 개수가 클 수록 해당하는 문제들을 푸는 것이 가장 많은 컵라면을 획득할 수 있습니다. 이..

https://www.acmicpc.net/problem/1484 1484번: 다이어트 첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우 www.acmicpc.net 안녕하세요. 투포인터 문제 입니다. 간단하게 말하면, x^2 - y^2 = G 가 되는 x를 구하는 문제입니다. 하지만, 문제에는 G의 값만 주어졌습니다! 이런.. 그럼, x와 y를 하나씩 선택해서 제곱한 값이 G와 일치하는지 일일히 비교해야하나?? 이렇게 되면, 최소 시간복잡도는 O(n^2)이 되는데, 이 n의 값(최대 범위)을 잡으려고 보니 G N = 50000 정도 2) 초기 제곱값을 배열에 저장해..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 안녕하세요. 이 문제는 투포인터 문제 입니다. 10000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어지는데요. 이 수열에서 연속된 수들의 부분합 중 S 이상이 되는 수들 중 가장 짧은 것의 길이를 구해야합니다. 알고리즘 먼저, 1) start와 end를 0으로 초기화 한 후 while문에 진입하는데요. 초기 합은 index 0인 값으로 설정합니다. while문 진입 시 2) 지..

https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 안녕하세요. 투포인터를 사용하는 문제입니다. 하지만, start ~ end 길이가 고정된 길이기 때문에, sliding window 알고리즘이라고도 할 수 있겠죠. 위 그림이 회전초밥이라고 해서 마치 원형처럼 느껴져서 처음에 당황해하실 수 있는데요. 알고보면 간단합니다. 배열 길이(N개) 이상 넘어가면 해당 배열 길이만큼 % 연산을 수행하면 되니까요! 나머지..