김머성 블로그

[BAE/<JOON> 문제풀이] 15678. 연세워터파크 / 11003. 최솟값 찾기

https://www.acmicpc.net/problem/15678 15678번: 연세워터파크 첫 줄에 징검다리의 수 N과 문제에서 설명한 D가 주어진다. (2 ≤ N ≤ 105, 1 ≤ D ≤ N-1) 이어 N개의 정수로, 각 징검다리에 쓰인 수 Ki가 1번 징검다리부터 N번 징검다리까지 순서대로 주어진다. (-109 www.acmicpc.net https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 서론 서로 완전히..

[BAE/<JOON> 문제풀이] 17251. 힘 겨루기

https://www.acmicpc.net/problem/17251 17251번: 힘 겨루기 과거 격투가로 명성을 떨치던 힘스트롱씨는 "힘 겨루기"라는 대회를 주최하여 전국에 홍보를 하였다. 모집 공고를 보고 전국 각지에서 많은 사람들이 모였는 데, 모집 공고에 '힘'이란 것에 대해 www.acmicpc.net 서론 골랜디한답시고 비장하게 랜덤돌렸는데 골드5 나옴. 잘먹겠습니다. 풀이 가장 힘 쎈 애가 있는 구간을 파악한다. 각각 s1, s2라고 정하면 3개의 구간이 만들어지며 승패는 다음과 같다. 1 ~ s-1 구간 청팀 승 s1 ~ s2-1 구간 무승부 s2 ~ n 구간 홍팀 승 따라서 승률은 1번 구간과 2번 구간 수의 비일 것이다. 각 구간의 개수를 구해 답을 출력하면 된다. 코드 더보기 #inc..

[BAE/<JOON> 문제풀이] 2655. 가장 높은 탑 쌓기

https://www.acmicpc.net/problem/2655 2655번: 가장높은탑쌓기 첫째 줄에는 입력될 벽돌의 수가 주어진다. 입력으로 주어지는 벽돌의 수는 최대 100개이다. 둘째 줄부터는 각 줄에 한 개의 벽돌에 관한 정보인 벽돌 밑면의 넓이, 벽돌의 높이 그리고 무게가 차 www.acmicpc.net 서론 DP 라서 배낭부터 생각했는데 그래프를 가미한 문제였다. 읽은 순간에는 돌끼리 절대 쌓는 순서가 바뀔 수 없으니 그래프로 짜야겠구나 싶다가도 태그보면 DP라 웰논에 매몰돼버린다. 태그 안보고 풀어야 하는데 골랜디 너무 어려워.. 풀이 서론에 써놓았듯, 돌끼리는 서로 방향 그래프 관계에 있다. 어떤 돌 위에 쌓을 수 있는 가장 높은 탑을 구하고 그 주춧돌에 대해 다시 재귀적으로 같은 로직을..

[BAE/<JOON> 문제풀이] 2228. 구간 나누기

https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net 서론 DP 문제를 모르겠으면 DP 테이블 배열에 들어갈 요소 무조건 정하고 억지로라도 점화식 만들어 수정하는게 나은 것 같다. 그렇게 해야 최소한 풀이 힌트 건덕지라도 나온다. 풀이 우선 복수의 구간 없이 단일 구간 합의 최대를 구하는 알고리즘을 생각해보자. 점화식은 dp[i] = max(dp[i - 1] + arr[i], arr[i]) 이다. 문제에서 구하는 답은 서로 ..

[BAE/<JOON> 문제풀이] 3687. 성냥 개비

https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 서론 휴일이라 쉬운거 골라야하는데 DP는 이상하게 문제만 보면 다 쉬워보인다. 막상 짜면 코너케이스도 많고 심지어 점화식 자체가 잘못된 경우도 있음.. 솔직히 이 문제 고르기 전으로 시간 되돌리고 싶다. 풀이 점화식은 사용한 성냥 개수와 그에 따라 만들어지는 수의 [만들어진 숫자 중 0을 제외한 가장 작은 수], [만들어진 숫자 개수] 가지 정보를 활용했다. 큰 수의 경우는 가장 앞에 0이 오면 안된다는..

[BAE/<JOON> 문제풀이] 2157. 여행

https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 서론 KCM Travel 열화 버전 문제. 최적이 아닌 탐색도 유지해야한다는 점이 같다. 풀이 KCM 과의 차별점은 정점을 항상 오름차순으로만 방문하도록 제한된다는 점(1) 탐색 줄기 정보 중 하나가 방문 정점 개수이므로 현재 줄기 유지 여부를 상수 시간에 판단 할 수 있다는 점(2)이다. 각각 풀어서 설명하면 다음과 같다. (1) :..