Loading [MathJax]/jax/output/CommonHTML/jax.js

분류 전체보기

220912 문제 풀이 기록

2022. 9. 13. 02:36

*800 | 1702A. Round Down the Price

풀이 시간: 무려 +12분

시도 횟수: 무려 2회

체감 난이도: B3

풀이 쓸 의향: 下

풀이

더보기
  1. while (ans*10 <= n) ans*=10;
  2. cout << n-ans << "\n";

여담: 문제를 잘못읽고 냈다가 안보고 B풀고 나서 다시품

 

 

 

*800 | 1702B. Polycarp Writes a String from Memory

풀이 시간: 10분

시도 횟수: 1회

체감 난이도: B1

풀이 쓸 의향: 下

풀이

더보기

단순 브루트포싱 및 구현.

여담: string 관련 구현을 너무 못하는...

 

 

 

*1100 | 1702C. Train and Queries

풀이 시간: 13분

시도 횟수: 1회

체감 난이도: S1

풀이 쓸 의향: 下

풀이

더보기

map으로 가장 왼쪽 / 오른쪽 저장해놓은 상태에서 풀기

여담: 단순 map 구현 문젠데 생각보다 오래걸려버림 ㅠ

 

 

 

*1000 | 1702D. Not a Cheap String

풀이 시간: 5분

시도 횟수: 1회

체감 난이도: S3

풀이 쓸 의향: 下

풀이

더보기

greedy하게 가장 높은 비용의 letter 하나씩 빼기

여담: C>>D Forces..

 

 

 

*1600 | 1702E. Split Into Two Sets

풀이 시간: 30분

시도 횟수: 2회

체감 난이도: G3

풀이 쓸 의향: 中

풀이

더보기

그래프로 구현하여 그래프 노드 개수가 전부 짝수면 YES, 아니면 NO

여담: 참신한 문제

 

 

 

*1700 | 1702F. Equate Multisets

풀이 시간: 40분

시도 횟수: 4회

체감 난이도: G3

풀이 쓸 의향: 下

풀이

더보기

배열 a의 원소가 모두 홀수가 될때까지 전부 2로 나눠준 뒤, b를 계속 나누면서 a의 원소가 되는지 확인. multiset 쓰면 편함.

여담: a의 원소가 짝수면 무조건 되는줄 착각하고 -1, multiset 1일때 고려 안해서 -2;

 

 

 

*800? | 1729A. Two Elevators

풀이 시간: 무려 6분

시도 횟수: 무려 2회

체감 난이도: B3

풀이 쓸 의향: 下

풀이

더보기

단순 구현

여담: 문제 잘못 읽고 -1;

 

 

 

*800? | 1729B. Decode String

풀이 시간: 7분

시도 횟수: 1회

체감 난이도: B1

풀이 쓸 의향: 下

풀이

더보기

단순 구현

여담: string 구현이 좀 귀찮음

 

 

 

*1000? | 1729C. Jumping on Tiles

풀이 시간: 무려 20분

시도 횟수: 무려 2회

체감 난이도: S4

풀이 쓸 의향: 下

풀이

더보기

(시작점, 끝점)이 오름차순이면 오름차순 모든 letter 순회, 내림차순이면 내림차순으로 순회;

여담: 내림차순 처리 안해놓고 왜틀렸는지 몰라서 시간 좀 많이 날림...

 

 

 

*1100? | 1729D. Friends and the Restaurant

풀이 시간: 10분

시도 횟수: 1회

체감 난이도: S1??

풀이 쓸 의향: 下

풀이

더보기

[갖고 있는 돈 - 내야 하는 돈] 오름차순 정렬해두고 투포인터 그리디

여담: 풀이 시간 < 구현 시간 < 문제 이해 시간

 

 

 

*1600???? | 1729E. Guess the Cycle Size

풀이 시간: 50분!!!!!!!

시도 횟수: 무려 12회;

체감 난이도: X

풀이 쓸 의향: 下

풀이

더보기

(1 2) / (2 1),  (2 3) / (3 2) ... 같이 (a b) (b a) 번갈아 쿼리 날리면 1/2^25 확률로 틀리니 사실상 맞음

여담: 이건... 쉬운데.... 뭐지 이게;

 

 

 

*1800 | 1729F. Kirei and the Linear Function

풀이 시간: 1시간

시도 횟수: 무려? 6회

체감 난이도: G1

풀이 쓸 의향: 下

풀이

더보기

(a*b)%c = ((a%c) * (b%c))%c, (a+b)%c = (a%c + b%c)%c이며, 9로 나눈 나머지는 항상 모든 자리수의 합을 9로 나눈 나머지와 같다는 사실을 이용하자.

부분합을 활용해 각 테스트케이스마다 각 시작점에서의 substring을 9로 나눈 나머지를 알 수 있고, 나머지 값은 0부터 8까지이므로 각 쿼리마다 9^2 순회 돌면서 확인하면 됨.

여담: 초기화를 쿼리 while안이 아니라 TC while안에서 바꿔주는 기열찐빠짓을 저지르는 바람에 시간 안에 못풀었음....

아 아직도 화나네 ㅋㅋㅋㅋㅋㅋㅋ

 

'PS > 풀이 기록장' 카테고리의 다른 글

220915 문제 풀이 기록  (0) 2022.09.15
220913 문제 풀이 기록  (0) 2022.09.13
220911 문제 풀이 기록  (0) 2022.09.11
220910 문제 풀이 기록  (0) 2022.09.11
220909 문제 풀이 기록  (0) 2022.09.10

220911 문제 풀이 기록

2022. 9. 11. 18:56

P5 | 17489 - 보물 찾기

풀이 시간: 40분

시도 횟수: 2회

체감 난이도: G1 상위권

풀이 쓸 의향: 下

풀이

더보기

(시작점, 끝점)으로 구성되는 그래프를 형성한 뒤에, (1, 1)에서 시작하는 점 중 가장 멀리 있는 점 출력. 이때, 사이클이 생기면 -1 출력.

여담: 솔직히 P5는 아닌것 같다 싶긴 했지만, 그래도 구현이 조금 까다로워서... P5 받을만도 하지 않나 싶었다.

 

 

오늘은 다른 프로젝트를 진행하느라 문제는 이거 하나만...

 

 

'PS > 풀이 기록장' 카테고리의 다른 글

220913 문제 풀이 기록  (0) 2022.09.13
220912 문제 풀이 기록  (0) 2022.09.13
220910 문제 풀이 기록  (0) 2022.09.11
220909 문제 풀이 기록  (0) 2022.09.10
220908 문제 풀이 기록  (0) 2022.09.10

220910 문제 풀이 기록

2022. 9. 11. 18:36

G5 | 13910 - 개업

풀이 시간: 약 10분

시도 횟수: 5회

체감 난이도: G4

풀이 쓸 의향: 下

풀이

더보기

기본 냅색 DP

여담: div3 버추얼 돌리기 전에 빠르게 풀어봄.

 

 

 

*800 | 1714A. Everyone Loves to Sleep

풀이 시간: 3분

시도 횟수: 1회

체감 난이도: B1

풀이 쓸 의향: 下

풀이

더보기

시간을 분으로 바꿔서 나타내자

여담: 곧 있을 div3 대비? 코포 버추얼. 어차피 div3은 unrated긴 한데 재미로 해봄.

 

 

 

*800 | 1714B. Remove Prefix

풀이 시간: 3분

시도 횟수: 1회

체감 난이도: B1

풀이 쓸 의향: 下

풀이

더보기

맨 뒤에서부터 하나씩 값 추가하면서 distinct 하지 않은 index 출력하기

여담: A보다 쉬운 B

 

 

 

*800 | 1714C. Minimum Varied Number

풀이 시간: 5분

시도 횟수: 1회

체감 난이도: S4?

풀이 쓸 의향: 下

풀이

더보기

앞부분 오름차순, 뒷부분 오름차순을 잘 엮으면 됨.

여담: 사실... 그냥 손으로 다 쓴 다음에 정답 45개 복붙해서 배열에 박았음. 코드 구현보다 이게 더 빠를것 같아서..

 

 

 

*1600 | 1714D. Color With Occurences

풀이 시간: 22분

시도 횟수: 1회

체감 난이도: G4?

풀이 쓸 의향: 下

풀이

더보기

텍스트 t에 대해 앞에서부터 차례대로, 최대한 오른쪽까지 커버 가능한 string 골라서 넣기. 하다가 안되면 -1

여담: 난이도가 무슨 ABC<<<E<D 느낌이었음... div3 난이도 맞추기가 상당히 어려워 보이긴 하는데...

 

 

 

*1400 | 1714E. Add Modulo 10

풀이 시간: 18분(-3분)

시도 횟수: 1회

체감 난이도: G5?

풀이 쓸 의향: 下

풀이

더보기

mod 10이 0일때, 5일때, 그 외 나눠서 보면 0이나 5면 무조건 각각 0번, 1번 더하면 더이상 바뀌지 않고, 나머지는 모두 2,4,6,8 돌아가며 나온다. mod 10이 2일때로 모두 고정한 뒤 (x/10)%2값이 하나라도 다르면 NO, 다 같으면 YES

여담: 풀면서 재밌었던 문제. 안타깝게도 이거 풀고나서 힘이 쭉 빠져서 E는 못풀었다... ;(

'PS > 풀이 기록장' 카테고리의 다른 글

220912 문제 풀이 기록  (0) 2022.09.13
220911 문제 풀이 기록  (0) 2022.09.11
220909 문제 풀이 기록  (0) 2022.09.10
220908 문제 풀이 기록  (0) 2022.09.10
220907 문제 풀이 기록  (0) 2022.09.08

220909 문제 풀이 기록

2022. 9. 10. 01:12

P3 | 16909 - 카드 구매하기 3

풀이 시간: 1시간 + a

시도 횟수: 1회

체감 난이도: P3

풀이 쓸 의향: 下

풀이

더보기

빼지는 값은 top이 작은 수가, 더해지는 값은 top이 큰 수가 오도록 해서 monotone stack을 두번 사용하여 합하기.

여담: 졸린 나머지 코드를 너무 난잡하게 짰다...

'PS > 풀이 기록장' 카테고리의 다른 글

220911 문제 풀이 기록  (0) 2022.09.11
220910 문제 풀이 기록  (0) 2022.09.11
220908 문제 풀이 기록  (0) 2022.09.10
220907 문제 풀이 기록  (0) 2022.09.08
220906 문제 풀이 기록  (0) 2022.09.06

220908 문제 풀이 기록

2022. 9. 10. 00:23

G5 | 2759 - 팬케이크 뒤집기

풀이 시간: 15분

시도 횟수: 1회

체감 난이도: G5

풀이 쓸 의향: 下

풀이

더보기

가장 큰거 맨 위로 올렸다 내리기 반복

여담: 코포 전 잠깐 연습용으로 풀어본 문제

 

 

 

이러고 나서 코포 조졌는데, 아... 너무 아깝다.... 점수가 오르긴 했는데 D번을 시간 안에 못푼게 너무 아쉬워서 빨리 다음 코포 하고싶다.

'PS > 풀이 기록장' 카테고리의 다른 글

220910 문제 풀이 기록  (0) 2022.09.11
220909 문제 풀이 기록  (0) 2022.09.10
220907 문제 풀이 기록  (0) 2022.09.08
220906 문제 풀이 기록  (0) 2022.09.06
220905 문제 풀이 기록  (0) 2022.09.05

220907 문제 풀이 기록

2022. 9. 8. 19:47

P4 | 8903 - 장비

풀이 시간: 40분

시도 횟수: 2회

체감 난이도: P4

풀이 쓸 의향: 下

풀이

더보기

K>=5 일땐 각각의 최대 구하기, K<5 일땐 각각 r1의 최대, ... ,r5의 최대, r1+r2의 최대, r1+r3의 최대, ... , r1+r2+r3+r4+r5의 최대 각각 메모이제이션 해놓고 브루트 포싱

여담: 저번에 풀었던 Baseball Watching 문제와 비슷한 브루트 포싱 문제. 왠진 모르겠는데 이런 문제 참 좋다.. 뭔가 색다른 느낌

 

 

'PS > 풀이 기록장' 카테고리의 다른 글

220909 문제 풀이 기록  (0) 2022.09.10
220908 문제 풀이 기록  (0) 2022.09.10
220906 문제 풀이 기록  (0) 2022.09.06
220905 문제 풀이 기록  (0) 2022.09.05
220904 문제 풀이 기록  (0) 2022.09.04

https://www.acmicpc.net/problem/6132

 

6132번: 전화선

[3, 3, 5, 3, 4] 로 전신주의 높이를 바꾸면 15에 문제를 해결할 수 있으며 이것이 최소다.

www.acmicpc.net

 

* 해당 풀이는 정해와는 다른 풀이입니다.

 

1. 문제

- N(100,000)개의 전신주의 높이 Hi(100)와 정수 C(100)가 주어진다.

- 총 비용은 C||의 합으로 이루어진다.

- 전신주의 높이를 X만큼 높이면 비용은 X2만큼 늘어난다.

- 가능한 비용의 최솟값을 구하시오.

 

 

2. 힌트

 

힌트 1

더보기

당연하게도, 높이가 이미 최대인 전신주의 높이는 올릴 필요가 전혀 없다. 또한, 문제 조건에 의해, 대부분의 경우 높이가 최소인 전신주의 높이는 올리는 것이 최적이다.

 

힌트 2

더보기

높이가 최소인 전신주의 왼쪽/오른쪽 전신주의 높이 중 하나라도 그 전신주의 높이보다 낮거나 같으면, 높이가 최소인 전신주의 높이를 올리지 않는 것이 최적일 가능성이 있다. 이 때 전신주의 높이를 올려야할지 말아야할지는 어떻게 선택해야 할까?

 

힌트 3

더보기

어떤 전신주의 좌/우 높이 중 하나라도 작은 것이 있다면, 반드시 더 작은 전신주를 먼저 올리고 보는 것이 좋다.

 

 

3. 문제 관찰 과정 및 풀이

 

처음 문제를 봤을 땐, 정말 답도 없게 느껴졌다. 뭔가 수학 문제 같기도 하고... 어떤 전신주를 올려야 최적인지에 대해 고민해봤다.

일단 처음 관찰했던 것은, 당연히도 높이가 최대인 전신주는 처음부터 끝까지 건드릴 일이 전혀 없다는 것이다.

해당 전신주는 높여봤자 이득 보는것이 전혀 없기 때문이다.

그렇다면 최소인 경우는 어떨까? 거의 대부분의 경우에는 1은 올리는 것이 최적이지만, 최소인 것이 여러개 동시에 있다면 해당 전신주를 올리지 않는 것이 최적일 수도 있다.

왜냐하면 이웃한 전신주 중 해당 전신주와 높이가 동일한 것이 하나라도 존재한다면 해당 전신주를 높였을 때 얻는 비용 이득 없이 (X+1)2X2만큼의 손해만 보기 때문이다.

 

여기서 중요한 관찰이 이미 등장했는데, 사실 못보고 지나쳤다. 잠시 DP를 생각하다가, 저주받은 DP 실력에 의해 한번 밀려나가 풀이 노트를 뚫어져라 쳐다보던 중, 위의 노트를 다시 보았다.

이웃한 전신주 중 하나라도 높이가 같거나 낮은게 있다면 그 즉시에는 얻는 비용 이득 없이 (X+1)2X2만큼의 손해만 본다..?

그런데 그렇다면 이웃한 전신주들 중 하나라도 높이가 같거나 낮다면 해당 전신주를 올리지 않는것이 최적인가? 하면 그것은 아닌 것이, 해당 전신주와 높이가 같거나 낮은 전신주를 동시에 올리면 비용이 더 낮아질 수도 있기 때문이다.

 

여기서 드는 의문. 그렇다면 높이가 같은 전신주 두 개가 서로 붙어 있으면, 동시에 높이를 높이는 것이 최적일까?

그리고 잘 생각해 보면, 두 전신주 중 하나의 높이를 올리지 않으면 위에서 언급한 바와 같이 아무런 비용 이득 없이 (X+1)2X2만큼의 손해만 보게 되므로, 당연히 이는 사실이라고 할 수 있다.

 

또한 중요한 관찰이 하나 더 있는데, 작은 전신주부터 차례대로 그리디하게 높이를 올려보는 것이 반드시 최적이라는 것이다.

즉, 작은 전신주부터 "지금 올렸을 때 당장 비용이 줄어든다면 올리고, 아니면 더 이상 올리지 않는다" 라는 것이다.

작은 전신주 입장에서 보았을 때, 양 옆의 전신주가 얼마나 더 높아지는지와 큰 관계 없이 어차피 높이 1 차이당 C만큼의 비용 손해를 보게 된다.

그러나, "이웃한 전신주 중 하나라도 해당 전신주보다 작은 것이 있다면 올리지 않는 것이 최적이다" 라는 사실을 잘 생각해 보자.

만약 현재 비용 손해를 감수하고 해당 전신주를 올렸더라도, 어차피 양 옆의 전신주가 해당 전신주보다 크다면 어차피 해당 전신주로 인한 비용 이득은 더 이상 존재하지 않는다. (어떤 전신주의 비용 이득 / 손해는 전적으로 이웃한 전신주에만 관계가 있기 때문이다)

 

따라서, 가장 작은 높이의 연속된 구간을 그리디하게 하나씩 올려보며 비용 이득이 생기면 해당 구간의 높이를 올리고, 아니면 그대로 두는 방식으로 코드를 구현하면 된다.

구현 방식은 여러가지겠지만, 필자는 pq<tuple<int, int, int>>를 사용하여 해결하였다. 만약 pq.top()이 지금 막 올리려는 높이와 같다면 구간을 합쳐주는 방식으로 구현하면, 약 NlgN 안에 해결 가능하다.

또한, 높이는 최대 Hmax까지만 올리므로, 위의 연산을 Hmax만큼 반복하면 총 시간 복잡도는 약 NHmaxlgN 이다.

제한 시간이 1초라는 점을 감안하면 조금 빡빡하다 생각될 수 있지만, 어차피 올리는 높이가 2C만 넘어가도 무조건 올리지 않는 것이 최적이므로 최악의 경우에도 2CNlgN 정도의 시간 안에 가능하며, 이는 굉장히 널널한 시간이다.

 

4. 코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    int n, c, h[100005], a[100005];
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    cin >> n >> c;
    int p = 0;
    for (int i=1; i<=n; i++) {
        cin >> h[i];
        a[i] = h[i];
        pq.push({h[i], i, i});
    }
    
    for (int i=1; i<n; i++) {
        p += abs(h[i+1] - h[i]) * c;
    }
    while (!pq.empty()) {
        int val, l, r;
        tie(val, l, r) = pq.top();
        pq.pop();
        
        while (!pq.empty() && val == get<0>(pq.top()) && get<1>(pq.top()) == r+1) {
            r = get<2>(pq.top());
            pq.pop();
        }
        
        
        int penalty = 0;
        for (int i=l; i<=r; i++) {
            penalty += (val + 1 - h[i]) * (val + 1 - h[i]) - (val - h[i]) * (val - h[i]);
        }
        if (l!=1)   penalty += (a[l-1] > a[l]) ? -c : c;
        if (r!=n)   penalty += (a[r+1] > a[r]) ? -c : c;
        if (penalty < 0) {
            p += penalty;
            pq.push({val+1, l, r});
            for (int i=l; i<=r; i++)    a[i] = val+1;
        }
    }
    
    cout << p;
}

5. 여담

비록 정해는 아니지만, 이런 그리디 아이디어 자체는 상당히 훌륭하고 재밌는 아이디어인 것 같다. 풀자 마자 글을 쓰고 싶었던 문제 중 하나.

정해 풀이는 DP 풀이인것 같은데, 풀고 나서 죄다 DP 태그가 박혀 있길래 USACO editorial까지 찾아보니까 거기서도 dp로 풀고 있었다. 사실 시간 복잡도 자체는 비슷해서 딱히 상관은 없고, 그냥 새로운 풀이 정도의 느낌.

220906 문제 풀이 기록

2022. 9. 6. 23:02

P5 | 23760 - 까다로운 아이들과 선물 상자

풀이 시간: 20분+25분

시도 횟수: 4회

체감 난이도:  P5

풀이 쓸 의향: 下

풀이

더보기

세그트리 이분탐색. 사탕상자 문제처럼 풀면 되는데, 사실 그생각을 못해서 그냥 k로 이분탐색 조져서 k이상 숫자의 개수로 이분탐색 돌려서 N(lgN)^2 풀이가 됨..

여담: 풀이 시간이 20분 + 25분인 이유는 처음에 문제를 잘못 읽었기 때문... 1번 아이부터 M번 아이까지 순서대로 선물을 가져가는게 아니라, 최적의 순서로 아이들을 놓았을 경우 가능한지를 묻는 문제인줄 알았다. 풀고 나서 예제 넣어봤는데 답이 이상하게 나와서 다시 보니까 순서대로 놓는거였다.... 아니 최적의 순서로 아이들 놓는 문제도 풀이 재밌고 좋은데 ;(

시도 횟수 4회는... 빠르게 틀린 이유 3개 찾아서 파바박 넣었다. 아니 이럴거면 제출 전에 좀 보지....

 

'PS > 풀이 기록장' 카테고리의 다른 글

220908 문제 풀이 기록  (0) 2022.09.10
220907 문제 풀이 기록  (0) 2022.09.08
220905 문제 풀이 기록  (0) 2022.09.05
220904 문제 풀이 기록  (0) 2022.09.04
220903 문제 풀이 기록  (0) 2022.09.04

220905 문제 풀이 기록

2022. 9. 5. 23:09

P3 | 13134 - Baseball Watching

풀이 시간: 1시간 30분

시도 횟수: 1회

체감 난이도: P3

풀이 쓸 의향: 中

풀이

더보기

가능한 모든 경우인 3^9에 대해, i번 학생이 절대로 걸리지 않는 2^9경우를 저장한 뒤 최대/최소 출력.

여담: 풀이 중간에 풀이를 한번 떠올렸다가 갑자기 이상한 코드를 짜기 시작하더니 미궁으로 빠져버린 요상한 케이스... 근데 문제 아이디어가 참 마음에 들었다. 일반적인 최적화 문제만 풀다 이런 문제 푸니까 머리가 어지럽다...

 

 

 

P5 | 19580 - 마스크가 필요해

풀이 시간: 10분

시도 횟수: 1회

체감 난이도: P5?

풀이 쓸 의향: 中

풀이

더보기

회의실 배정 문제와 비슷한 유형. 구간 [l, r]을 l 기준으로 오름차순 정렬하고 가격 x도 오름차순으로 정렬해둔 뒤, l<=x이면 pq에 r만 오름차순으로 넣고, r>=x이면 ans++, 아니면 pop;

여담: 내가 좋아하는 유형의 문제라 상당히 빠르게 풀 수 있었던 것 같다. 그 리 디 조 아

사실 풀이가 처음 머리에 딱 박혀서 빠르게 풀긴 했지만, 구현하는 방식도 까다롭기도 하고 머리에 풀이가 빠르게 안박혔으면 풀기 많이 힘들었을 듯 하다.

 

 

 

 

'PS > 풀이 기록장' 카테고리의 다른 글

220907 문제 풀이 기록  (0) 2022.09.08
220906 문제 풀이 기록  (0) 2022.09.06
220904 문제 풀이 기록  (0) 2022.09.04
220903 문제 풀이 기록  (0) 2022.09.04
220902 문제 풀이 기록  (0) 2022.09.04

220904 문제 풀이 기록

2022. 9. 4. 23:57

G5 | 25513 - 빠른 오름차순 숫자 탐색

풀이 시간: 10분

시도 횟수: 1회

체감 난이도: G5

풀이 쓸 의향: 下

풀이

더보기

그냥 BFS문제. 6번 BFS 돌리자.

여담: 골드 조지기 시작!

 

 

 

G4 | 4179 - 불!

풀이 시간: 25분

시도 횟수: 6회

체감 난이도: G3

풀이 쓸 의향: 下

풀이

더보기

그냥 BFS긴 한데 구현이 조금 까다롭다. 불 시뮬레이션 잘 해주자.

여담: 어제의 구현 까다로운 BFS에 이은 두 번째 구현 까다로운 BFS. 음... 내가 이런 문제쪽에 약한가보다.

 

 

 

G3 | 14595 - 동방 프로젝트

풀이 시간: 7분

시도 횟수: 1회

체감 난이도: G4

풀이 쓸 의향: 下

풀이

더보기

room[x] = x로 초기화한 다음, room[x] = max(room[x], y)로 바꿔준 뒤 구간 그리디.

여담: 자칫 유니온&파인드를 구현해서 풀어야 할 문제처럼 보일 수 있지만, 그냥 정렬하거나 위의 풀이처럼 풀면 쉽게 풀린다.

 

 

 

G2 | 17942 - 알고리즘 공부

풀이 시간: 1시간

시도 횟수: 11회

체감 난이도: G2

풀이 쓸 의향: 下

풀이

더보기

pq 그리디로 작은 숫자부터 채우기. 다익스트라랑 유사함.

여담: 처음엔 매개변수 탐색으로 풀다가, 왜인지 모른 맞왜틀 끝에 그냥 빠르게 구현 수정해서 매개변수 탐색 없이 내니까 됐음.

아니 근데 매개변수 탐색 있이 풀어도 똑같은 코드인데 왜틀렸지...??? 하고 있었는데 별 미친실수를 다했었네..... 미친건가 진짜?

'PS > 풀이 기록장' 카테고리의 다른 글

220906 문제 풀이 기록  (0) 2022.09.06
220905 문제 풀이 기록  (0) 2022.09.05
220903 문제 풀이 기록  (0) 2022.09.04
220902 문제 풀이 기록  (0) 2022.09.04
220901 문제 풀이 기록  (0) 2022.09.01

+ Recent posts