1강 브루트 포스 - 건너 뛰며 해보기

우왕 나 이제 실버야!! 방학동안 100문제 풀었다!! 얼른 이 강의 다 듣고 강의 문제 풀고 끝나면 나머지 DP문제 안푼거 하루에 하나씩은 꼭꼭 풀어봐야지!! 종만북도 읽을거야!! 학교 공부도 블로그에 정리해가면서 할거라구~~ 화이또!!

아임 실버

강의듣고 올게요~

-----------------------------------------------------------------------------------------------------------------------------------

 

-건너 뛰며 해보기

전에는 모든 경우의 수를 다해보는 방법으로 구했다면 이번엔 다 구하지 말고 건너 뛰면서 해보도록 한다.

 

<6064번 / 카잉 달력>

M, N보다 작거나 같은 두 자연수 x, y를 이용하여 년도 <x:y>를 표현한다. 그 떄 몇번째 해인지 구하는 문제이다. 만약 이 문제를 모두 다 구하는 방법으로 한다면 M과 N의 범위가 4만까지이므로 전체 경우 MN은 너무 크다. 따라서 건너뛰며 구해보도록 한다. 

건너뛰며 구하기

여기서 만약 x를 3으로 고정하고 찾는다면 5번마다 검사하면 된다. (3은 주기가 5니깐) 아니면 얘도 위의 필기처럼 나머지 연산을 통해 구할 수 있다. 

따라서 x를 이용해 모든 해를 고려하지 않고, i*M+x (i>=0)의 형태만 조사하면 된다. 얘는 M을 고정한다면 N번만 조사하면 되기 때문에 시간 복잡도는 O(N)이 된다.

나머지 연산을 이용하여 구했다. (백준 알고리즘 코드 참고함)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#include <iostream> #include <algorithm> using namespace std; int main() {     int t;     cin >> t;     while (t--)     {         int m, n, x, y;         cin >> m >> n >> x >> y;         x--;         y--;         bool check = false;         for (int i = x; i < n*m; i += m)         {             if (i%n == y)             {                 check = true;                 cout << i + 1 << '\n';                 break;             }         }         if (check == false)         {             cout << -1 << '\n';         }     }     return 0; } Colored by Color Scripter

cs

 

<1748번 / 수 이어 쓰기 1>

1부터 N까지 수를 이어서 써서 새로운 하나의 수를 얻게 되는데 그 수의 자릿수를 구하는 문제이다. 이걸 실제로 해보기엔 N이 1억이기 때문에 너무 오래걸리게 된다. 이 문제는 수의 자리수별로 나누어서 문제를 해결할 수 있다. 만약 N이 120이라면 1-9, 10-99, 100-120 으로 자릿수별로 나눠서 문제를 해결할 수 있다. 이 방법은 이 문제에서 1~N까지 수가 빠짐없이 있기 때문에 가능하다. 그러면 위의 예시에선 아래처럼 구하면 된다.

코드는 간단하다. 자리수별로 나눠서 구한다. len이 자릿수, start는 1, 10, 100이 되고 마지막은 start*10-1로 해서 1-9, 10-99, 100-999,... 이런식으로 한다. 만약 end가 n보다 크면 end를 n으로 설정한 후 그 자릿수의 개수만큼 len을 곱해서 길이를 구하면 된다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include <iostream> #include <algorithm> using namespace std; int main() {     ios_base::sync_with_stdio(false);     cin.tie(nullptr);     int n;     cin >> n;     long long ans = 0;     for (int start = 1, len = 1; start <= n; start *= 10, len++)     {         int end = start * 10 - 1;         if (end > n)             end = n;         ans += (long long)(end - start + 1)*len;     }     cout << ans << '\n';     return 0; }

cs

 

- N중 for문

N개 중에 일부를 선택해야 하는 경우에 많이 사용한다. 재귀 호출이나 비트마스크를 사용하면 더 간결하고 보기 쉬운 코드를 작성할 수 있기 때문에, 사용할 일이 거의 없다. 

 

이 방법과 관련된 문제로는 9095번(1, 2, 3 더하기)에 적용할 수 있다. 이 문제의 n의 범위는 10보다 작거나 같기 때문에 n중 for문을 사용할 수 있다. 그래서 얘를 10중 for문으로 구현하면 된다. 이 방법은 약간 음... 극한의 필살기? 이런 느낌으로 생각하면 된다.

예시 코드

끄읕

뭔가 요즘 이게 맞나 싶기도 하고 하기싫은데 안하기도 그렇고,,,ㅠㅠㅠ

일단은 이 강의 끝까지 열심히 수강해보자 화이또!!!