[코드포스 Practice19] B. Segments

문제가 너무 이해 안 갔다..

 

?????? <- 이 상태로 5분동안 고민한 듯

 

그래도 어찌저찌 뭘 원하는지 이해했다

 

진짜.. 규칙 찾는다고 엄청 고민했다.

 

뭔가 재귀.. 막 그런거 쓰면 좋을 것 같다는 느낌 들었었다.

 

자기 이전 값에 뭔가를 더해가는 그런 게 있었음.

 

 

이러코롬..

 

이건 n이 6일 때인데 보면 최대 길이를 만들고 남은게 n = 4이다.

 

하지만 한 문제에 시간 너무 쓰면 안 될 것 같아서 어 규칙 있는데? 까지만 생각하고 C번으로 넘어갔다.

 

다시 돌아와서...

 

이대로면 1솔브겠다 싶어서 눈에 불키고 규칙 찾았다.

 

이런 규칙이 있다.

 

수학 똑똑이들은 등차수열 공식을 썼겠지만 맴이 급해서 그냥 반복문 돌렸다.

 

어차피 n이 100밖에 안 되는 거!

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
 
int main() {
    int n;
    scanf("%d", &n);
    
    vector <int>v(101);
    v[1] = 1;
    v[2] = 2;
    v[3] = 4;
    
    int sum = 4;
    for (int i = 4; i <= 100; i += 2)
    {
        v[i] = v[i-2] + sum;
        sum += 2;
    }
    sum = 5;
    for (int i = 5; i <= 100; i += 2)
    {
        v[i] = v[i-2] + sum;
        sum += 2;
    }
    
    cout << v[n];
    
    
    return 0;
}

 

코드는 이렇게 짰다.

 

배열 100칸 만들어서 반복문 돌렸다.

 

---

풀이를 봤다...!

 

아 이거 왼쪽 끝이 겹치면 다른 레이어로 취급하면 되구나!

 

그리고 오른 쪽 끝이 안 겹치면 합쳐도 되는 레이어이고.

 

신기하다!

 

 

근데 코드는 이해 못하겠다 ㅠ_____ㅠ

 

l은 시작 좌표인 것 같은데 r이 뭔지 모르겠음.

 

길이인가?? 싶었는데 길이는 1부터 n - l만큼 바뀌는게 아닌가 싶고

 

게다가 둘 다 1부터 n까지 돈다..

 

특히 ri를 r로 바꿔놓는 부분이 어렵다ㅠㅠㅠ 왜 r로 업데이트 시킬까??

 

북님...

 

그래서 위의 로직만 참고해서 내가 이해하기 쉽게 짜봤다.

 

 

일단 l은 왼쪽 좌표로 정의했다. 그래서 0부터 3만큼 돈다.

 

다음으로 r은 길이

 

r값은 l값에 따라 바뀌니깐 

 

for (int r = 1; r <= n - l; r++)

 

이렇게 돌게 했다.

 

그리고 레이어 벡터에는 오른쪽 끝 좌표를 넣어준다.

 

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#include <fstream>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
#define MOD ((int)(1e9 + 9))

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;


int main()
{
    int n;
    scanf("%d", &n);

    vector<int> layer;

    for (int l = 0; l < n; l++)
    {
        for (int r = 1; r <= n - l; r++)
        {
            bool ok = false;

            for (auto& ri : layer)
            {
                if (l >= ri)
                {
                    ri += r;
                    ok = true;
                    break;
                }
            }

            if (!ok)
                layer.push_back(l + r);
        }
    }

    printf("%d\n", layer.size());

    return 0;
}

 

다행히 맞았다