파게로그

문제 링크: 21316번 제목 https://www.acmicpc.net/problem/21316 "반드시 그림과 같은 모습임이 보장된다"에서, 그림을 통해 Spica의 특징(?), 즉 Spica를 변별해낼 수 있는 유일한 성질을 발견해야 한다는 것을 알 수 있다. 점 i와 연결되는 점의 개수를 f(i)라고 하고, 점 i와 연결되는 점을 i[1], i[2], ..., i[n]이라고 하면, Spica만 유일하게 f(i) = 3이면서 f(i[1])+f(i[2])+...+f(i[n]) = 6이다. 이 그림에서, Spica는 7이고, 7과 연결되는 점은 6, 3, 8이다. 그리고 f(6)= 1, f(3) = 3, f(8) = 2이다. 반면 f(i) = 3을 만족하는 다른 점들, 즉 3, 4, 9의 경우 f(i[..

문제 링크: 12865번 평범한 배낭 https://www.acmicpc.net/problem/12865 대표적인 풀이 방법은 2차원 DP 배열을 사용하는 방법으로서, 다음과 같이 생각해볼 수 있다. 참고로 보통은 부피라고 하는데 부피와 가치 둘 다 첫 문자가 v라 부피 대신 무게라고 하자. f(i, j) = 배낭에 넣을 수 있는 최대 무게가 j이고, i번째 물건까지 고려했을 때의, 최대 가치 f(i, j)는 어떻게 구할 수 있을까? 🤷‍♀️ 먼저, w(i)가 j보다 크다면? 이 때에는 물건 i를 배낭에 넣을 수 없다. 따라서 i번째 물건까지 고려했을 때의 결과는 i-1번째 물건까지 고려했을 때의 결과와 같아야 한다. 즉 f(i, j) = f(i, j-1) 🤷‍♀️ 그렇다면, w(j)가 i보다 같거나 작..

문제 링크: 17840번 피보나치 음악 https://www.acmicpc.net/problem/17840 N번째 수에 바로 접근하는 방법 나누는 수는 2 이상으로 정해져있는데, 그렇다면 나머지를 저장하는 수열은 반드시 0 1 1 ... 이런 식으로 이루어진다. 그렇다면 저 패턴이 다시 반복되면, 해당 패턴은 무한히 반복되는 것이다. 수열을 만들어가면서 1 1이 반복되면 그 때 멈추면 된다. 한 자리씩 떼어내서 세는 것을 어떻게 해야할까? fibo 배열과 digitList 배열을 따로 두어서 해결할 수 있다. 조심해야 할 점 아무 생각없이 나누면서 리스트에 집어넣어버리면 1의 자리부터 역순으로 들어가게 된다. import java.io.BufferedReader; import java.io.IOExcep..

문제 링크: 20191번 제목 https://www.acmicpc.net/problem/20191 문제에서의 S를 target이라 하고, T를 pattern이라 하자. alphas는 리스트의 배열로서, alphas[c]라는 리스트는 c라는 문자가 target에서 어디에 위치하는지에 대해 그 인덱스를 모두 담고 있다. 한편 patIdx라는, pattern을 가리키는 인덱스를 하나 둔다. 이는 pattern에서 마지막으로 사용된 문자의 위치를 가리키고 있으며, 초기값은 -1로 해둔다. 이는 뒤에 가서 그 이유를 알 수 있다. 우리는 for문 내에서 target을 한 글자씩 cur이라는 변수로 두고 채워나가는데, patIdx보다 뒤에 있는 문자만 사용 가능하다. 즉 alphas[cur]에서 patIdx보다 큰..

문제 링크: 1406번 에디터 https://www.acmicpc.net/problem/1406 스택 2개를 사용하거나, 덱 1개를 사용하거나 둘 중 편한 방법을 이용하면 된다. 덱을 선후가 있는 연결 리스트로 보았을 때 head는 커서 바로 오른쪽, tail은 커서 바로 왼쪽이라고 생각하면 된다. 그래서 커서를 왼쪽으로 옮길 때마다 마지막 것을 왼쪽으로 옮기고 하지만 환형 구조인 만큼 커서를 마지막에서 오른쪽으로 옮기면 처음으로 돌아온다든가 처음에서 왼쪽으로 옮기면 마지막으로 돌아간가든가 하는 것을 막지 못하기에, cursor 변수를 통해 이를 방지해야 한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputS..

문제 링크: 20206번 푸앙이가 길을 건너간 이유 https://www.acmicpc.net/problem/20206 [x1, x2]에서 일차함수 by=-ax-c(b!=0)은 최솟값과 최댓값을 지니며, ①최솟값이 위험 범위의 최대 y값보다 크거나 같으면, 또는 ②최댓값이 위험 범위의 최소 y값보다 작거나 같으면 푸앙이는 위험 지역을 지나지 않을 수 있다. 요컨대, by>-ax1-c && by>ax2-c || by -ax2 - c (a0)을 뜻하며, b=0일 때 dangerMiny, dangerMaxy는 모두 0이므로 코드에서의 판별 조건과 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRea..

문제 링크: 2346번 제목 https://www.acmicpc.net/problem/2346 풍선에 적힌 값을 나열한, 크기가 n인 배열 balloons를 선언한다. i가 n-1인 이유: 처음에 첫 풍선을 처리했기 때문 j의 의미: 풍선에 쓰인 숫자(num)만큼 cur을 옮기는데, 터진 풍선은 실제로는 이동하지 않은 것이기에 j를 통해서 실제 이동한 횟수를 세어준다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) thro..

문제 링크: 2840번 행운의 바퀴 https://www.acmicpc.net/problem/2840 크기가 n인 배열을 선언하고 rot번 돌렸을 때 해당 위치에 문자를 삽입해주며, %을 이용해서 맨 뒤 칸 다음 맨 앞 칸이 나올 수 있도록 한다. 실제로는 환형이므로 arrow의 초기값은 0이 아니라도 관계없다. 상덕이가 적어놓은 종이에 해당하는 행운의 바퀴가 없는 경우는 다음과 같다. ① 같은 칸에 다른 문자가 등장할 경우 → 비어있지 않은 칸일 경우 체크 ② 이미 등장한 문자가 다른 위치에 등장할 경우 → discover[] 배열로 해결 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;..