Jubil의 프로그래밍 블로그

1049_기타줄 링크 https://www.acmicpc.net/problem/1049 풀이 브랜드마다 6개 세트의 가격, 낱개의 가격이 주어지고 최소 가격으로 구매할 방법을 찾는 문제입니다. 그렇다면 6개 세트의 가격, 낱개의 가격이 모두 다 필요하지 않겠네요. 각각 최소 가격을 구합니다. n개의 줄을 사야할 때 (6개 세트 최소 가격)*(n/6) + (낱개 최소 가격)*(n%6)을 해주면 된다고 생각할 수도 있습니다. 하지만 애초에 6개 세트 최소 가격이 낱개로 6개 사는 것보다 크다면, 세트를 사는 것보다 낱개로 6개를 사는 것이 이득입니다. 또, 6개 세트 최소 가격이 낱개 최소 가격 * (n%6)보다 작다면 이것도 그냥 세트로 사는 것이 이득입니다. 따라서 이 두 상황을 고려해서 코드를 짜주면 ..

1032_명령 프롬프트 링크 https://www.acmicpc.net/problem/1032 풀이 우선 예제를 보면 문제를 더 쉽게 이해할 수 있습니다. 최소한의 '?'를 사용해서 나타내야 합니다. 그러면 모든 문장의 i번째 문자가 다 같다면 i번째 문자 그대로 출력하고, 다른 문자가 한 번이라도 쓰였을 경우 '?'를 출력해주면 됩니다. 그래서 저는 첫 번째 문장을 비교 대상으로 놓고 다른 문장들을 비교하는 방법을 사용했습니다. 코드

1026_보물 링크 https://www.acmicpc.net/problem/1026 풀이 배열의 원소의 곱의 합의 최솟값을 구해야 합니다. 그렇다면 큰 수는 작은 수와 곱해서 더하는 방식으로 구현하면 됩니다. B에 있는 수는 재배열이 안된다고 하지만, 최솟값을 구하는 문제이기 때문에 재배열을 해주도록 합시다. A를 오름차순으로, B를 내림차순으로 정렬해준 뒤, 서로 곱하고 더하면 됩니다. 코드

1009_분산처리 링크 https://www.acmicpc.net/problem/1009 풀이 문제를 읽어보면 수의 마지막 자리만 알아내면 됩니다. 항상 a^b로 주어지니 b를 1씩 줄이면서 a를 곱하고 10으로 나눈 나머지를 구하면 됩니다. 그 후, 결과값이 0인 경우에만 10을 출력하면 되는 것이죠. 코드

1002_터렛 링크 https://www.acmicpc.net/problem/1002 풀이 이 문제는 GPS 원리를 이용한 문제입니다. 2차원 평면이기 때문에 원래 3개의 터렛이 존재한다면 위치를 구할 수 있겠지만, 2개의 터렛만 있습니다. 이 문제는 두 원의 교점이 류재명이 있을 수 있는 위치가 됩니다. 두 원의 교점의 개수를 구하기 위해서 두 원의 위치 관계를 잘 이용해서 풀면 됩니다. 우선 거리와 반지름을 알아내야 합니다. 그리고 두 원이 일치할 때, 두 점에서 만날 때, 접할 때, 만나지 않을 때를 체크해서 구하면 됩니다. 코드

2167_2차원 배열의 합 링크 https://www.acmicpc.net/problem/2167 풀이 DP[i][j] (1

9465_스티커 링크 https://www.acmicpc.net/problem/9465 풀이 만약 별에서 시작했다면 1이나 2를 갈 수 있습니다. 하지만 2는 1을 거쳤다 갈 수 있기 때문에 1로 가야합니다. 이 상황도 마찬가지로 1로 가는 게 이득입니다. 그렇다면 위에서 시작했던 밑에서 시작했던 대각선으로만 가는 게 최선의 방법일까요? 아닙니다. 반례를 들어보면, 이렇게 대각선으로만 가면 102라는 값이 나오지만 최적이 아니라는 것을 알 수 있습니다. 이렇게 두 칸 전에서 오는 값도 체크해줘야 합니다. 세 칸 전에서 오는 건 충분히 더 많은 구역을 거칠 수 있기 때문에 보지 않아도 됩니다. DP[n][i]를 n번째 줄의 i번째까지 얻을 수 있는 최고의 점수라고 정의합니다. (n은 0~1, i는 1~10..

1149_RGB거리 링크 https://www.acmicpc.net/problem/1149 풀이 집 i의 이웃은 집 i-1과 i+1이고, 이웃은 같은 색으로 칠할 수 없습니다. DP[i][j] (집 i를 j색으로 칠했을 때까지의 최소 비용, j = 0 R, 1 G, 2 B) cost[i][j] (집 i를 j색으로 칠할 때의 비용, j = 0 R, 1 G, 2 B) 이라고 정의하겠습니다. 그렇다면 DP[i][0]은 이웃은 같은 색을 칠할 수 없다는 조건에 의해, min(DP[i-1][1], DP[i-1][2]) + cost[i][0]로 정의됩니다. (전에 다른 색 G, B로 칠했을 때까지의 최소 비용 + 현재 R로 칠했을 때의 비용) 즉, 나머지 색들도 생각해보면 다음과 같은 식이 나옵니다. DP[i][0..

1764_듣보잡 링크 https://www.acmicpc.net/problem/1764 풀이 STL의 map을 사용하면 python의 dictionary처럼 사용할 수 있습니다. 듣보잡 문제처럼 문자열을 인덱스로 사용해야 할 때, 아주 유용하게 사용할 수 있습니다. map mp 로 선언을 했다면, mp.first가 string을, mp.second가 int를 가리킵니다. 그리고 배열처럼 mp[mp.first]으로 mp.second에 접근할 수 있습니다. 코드

2075_N번째 큰 수 링크 https://www.acmicpc.net/problem/2075 풀이 오름차순 priority_queue를 이용해서 정렬해주면 됩니다. 코드