조금 응용된 BFS 문제이다. 이름은 귀엽지만, 문제는 귀엽지 않았다 ㅡ ㅡ 1. 출처 https://www.acmicpc.net/problem/1326 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net N개의 돌이 주어지고, 돌 위에는 점프할 수 있는 X배수가 써져있음 X*1, X*2, X*3... 이런식으로 1~N 돌 안에서 이동할 수 있음 목적지에 도착하기 위해 밟아야 하는 최소의 돌 수를 도출 도착할 수 없다면 -1 2. 설계 문제를 보면 출발지 < 도착지라는 보장이 없다. 때문에 우리는 출..
처음에는 '물통에 있는 물을 어떻게 규칙적으로 움직이지?' 라는 생각에 빠졌다. c->b, b->a 그 다음에는?... 흠... 설계가 떠오르지 않으니 당연히 알고리즘도 떠오르지 않았다 ㅋㅋ 1. 출처 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net A, B, C 물통 3개가 있음, 최대 200리터까지 올 수 있음 처음에는 C 물통이 가득 차있음 물통에 물을 이리저리 옮기다가 A가 0일 때 C에 올 수 있는 물의 리터를 오름차순으로 출력 2. 설계 설계는 알고나면 간단했다. 현재 A, B,..
구현문제처럼 풀었다가 맥도 못추린 문제... 싸피 때 양교수님께선 항상 말씀하셨지... "코드가 복잡하다는 느낌이 들면 아 내가 잘못하고 있구나" 항상 생각할 것... 2번의 불발된 시도 끝에 답안을 찾아보았다. 내가 가장 도움을 느낀 블로그는 이거다! https://yoggaebi.tistory.com/46 [백준, DP, JAVA] P.2299 조짜기 1. 아이디어 1. 입력값을 받을 때마다 해당 번째 위치에서 1번째까지 반복하며 조를 만들면서 최적의 값을 비교하여 가장 좋은 값을 선택 (1)우선 dp[0] = 0, dp[1] = 0으로 초기화 해줍니다. 0번째와 1 yoggaebi.tistory.com 글 자체는 이해가 되지 않았는데, 코드를 보며 한땀한땀 하다보니 이해가 팍 갔다! 1. 출처 ht..
왜 Arrays.sort를 계속 써도 시간초과가 나지 않는지 의문이었던 문제... 1. 출처 https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net N개의 카드가 주어짐 2장의 카드를 더한 값을 2장의 카드에 적용 == 카드합체 M번 카드 합체를 진행했을 때 모든 카드의 합이 가장 적게 나올 수 있는 경우를 구할 것 2. 설계 1. 타입은 long으로 카드 수는 최대 1000개가 나올 수 있고, 카드에 적힌 수는 ..
무려 4트만에 풀린 문제 ㅠㅠ 항상 밑그림이 끝나면 바로 코드를 짜는 버릇이 있는데, 예외 케이스를 최대한 많이 찾은 후 코드 설계를 해야한다는 게 너무 어렵다 ㅠ 1. 설계 https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 문서를 최대한 많이 찾으면 되는 문제 테스트케이스, 지도의 크기, 지도(빈공간, 문, 열쇠, 문서 위치), 내가 가진 열쇠들이 주어짐 상근이는 지도 밖에 있다가 지도 테두리에 들어올 수 있는 공간이 있으면 그 쪽으로 지도에 들어올 수 있..
오늘은 해당 문제로 시간 복잡도를 줄일 수 있는 설계에 대해 생각해볼 수 있었다. 1. 출처 https://www.acmicpc.net/problem/25487 25487번: 단순한 문제 (Large) 세 양의 정수 $a$, $b$, $c$가 주어질 때, 다음 조건을 만족하는 정수 쌍 $(x, y, z)$의 개수를 구하시오. $1 \le x \le a$ $1 \le y \le b$ $1 \le z \le c$ $(x\,\bmod\,y) = (y\,\bmod\,z) = (z\,\bmod\,x)$ $(A\,\bmod\,B)$는 $A$를 $B$ www.acmicpc.net (x%y) = (y%z) = (z%x) 에 부합하는 (x, y, z) 쌍이 몇 개인지 알아내는 문제 1
오늘 이분탐색 구현 방식에 따라 성능에 차이가 있다는 사실을 알았다. 왜 for문으로 투포인터 구현하면 시간 초과가 나고, while로 구현하면 통과인지 사실 아직도 모르겠다... 아는 고수 있으면 답변 주세요 ㅠㅠ 1. 출처 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net 2. 설계 1. 자바에서 불가능한 설계 처음에는 레고 조각 길이가 10cm = 10 * 10^7nm를 넘지 않는다고 해서 int[10*10^7+1]만큼 배열 공간을 확보해 갯수를 세주고 구멍의 너비 - 레고 조각의..
역시 dp는 어렵다... 오늘도 어김없이 답을 봤다. 답을 보면 다른 개발자분의 생각을 읽을 수 있다는 점에선 좋지만, 내 스스로 풀이 능력이 떨어지는 것 같아 항상 블로그에 글을 남긴다 ㅠ 1. 출처 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 각 스티커에는 점수가 붙어있다. 하나의 스티커를 뜯으면 4방에 인접해있는 스티커는 못쓴다. 최대 점수가 될 수 있게 스티커를 뜯자! 2. 설계 1. 오답 설계 - 그리디 사실 처음에는 난..
