Daily BOJ 22/01/01-22/01/09 - Haru.run

Daily BOJ 22/01/01-22/01/09

2022/01/09 # PS # solved.ac # Daily BOJ

⚠ 스포일러 주의 ⚠
이 글은 BOJ(백준 온라인 저지) 문제 해답을 포함하고 있습니다.

새해를 맞이해…

열심히 하겠습니다…!
1학기 개강 전에 1000 solve가 목표!!
- 방학동안 하루에 5문제+α로 풀기
정말정말정말정말 최대한 내 머리로 굴리고 도저히 못하겠으면 사람 붙잡고 구글 붙잡기…
잘 정리해서 기억하기. 귀찮다고 미루면 안됨. 나중에 뼈가되고 살이 된다…
- 실버이상의 문제부터 작성할 예정.

2022/01/02 일요일

#16155 업힐과 가희 [S1]

조사하려는 구간에 해당하는 높이를 구하면 좌표 두개가 나오는데
그 좌표의 기울기를 구하면 된다. 기울기를 구하는 공식 알면 그거 쓰면 됨.
분수로 나타내야해서 gcd(a, b)를 이용하면 된다.

struct slide{
    ll x, y;
};

slide a[60], ans;

구조체를 잘 쓰면 괜찮다. 기억하자

#5430 AC [G5]

그냥 너무 정직하게 풀면 시간초과가 당신을 기다리게 된다.
지우고 돌리고 하는데 $O(N)$만큼 걸린다고 들었다.
머리를 굴려야 한다!

int st = 0, ed = v.size()-1;
int r = false;
for(auto x: cmd){
    if(x=='R') r = !r;
    if(x=='D') {
        if(r==false) st++;
        else ed--;
    }
}

투포인터라고 해야하나 이걸

맨 처음(st)과 맨 끝(ed)에 기준선 변수 하나 두고, 진행 방향도 체크
D가 나오면 진행방향이 뭐냐에 따라서 st++하거나 ed--

#18258 큐 2 [S4]

q.push(), q.pop(), q.empty(), q.size(), q.front(), q.back() 사용
#10845 큐랑 무슨 차이인가 했더니 명령어의 수가 이게 더 크다$(1\le N\le2,000,000)$

#10974 모든 순열 [S3]

int N; cin >> N;
do{
    for(int i=0; i<N; i++) cout << a[i] << " ";
    cout << "\n";
} while(next_permutation(a, a+N));

next_permutation()을 쓰는 문제
생각보다 이거 많이 쓰인다고 하니깐 까먹지는 말자

#17218 비밀번호 만들기 [G5]

LIS, ‘가장 긴 증가하는 부분 수열’ 시리즈의 string버전이라고 생각이 들었다.

A="0"+A; B="1"+B;

for(int i=1; i<lenB; i++){
    for(int j=1; j<lenA; j++){
        if(A[j]==B[i]) dp[i][j] = dp[i-1][j-1]+1;
        else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    }
}

답을 냈으면 뒤에서 부터 추적을 해서 답을 도출해야하는데 잘 그림 dp그림을 봤으니 이걸 가지고 거꾸로 올라가면 된다.

#2225 합분해 [G5]

$_{k}{H}_{n} = _{k+n-1}{C}_{n}$ 구하는 문제
큰수가 나옴 && 귀찮아서 파이썬 이용했다.

1 2	import math ans1 = math.factorial(N)

#11656 접미사 배열 [S4]

1 2	string s; s.erase(0, 1);

s의 s[0]부터 1개를 지우는 함수
for문 돌면서 맨 앞을 날리며 vector<string>에 넣고 sort하면 알아서 잘 사전순으로 해줌

#11659 구간 합 구하기 4

누적 합 문제
s[i]: a[0]~a[i]까지의 합
a[i]~a[j]의 합: s[j]-s[i-1]

2022/01/03 월요일

#11778 피보나치 수와 최대공약수 [G2]

$gcd(F(a), F(b)) = gcd(a, b)$
n과 m이 1,000,000,000,000,000,000보다 작거나 같은 자연수라고 하니 행렬계산을 이용하변 될 듯.
$\begin{bmatrix} F_{n+1} \\ F_{n} \end{bmatrix}
= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{n} \\ F_{n-1} \end{bmatrix}
= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} 1 \\ 0 \end{bmatrix}$
행렬 곱셈도 반띵반띵하는 분할정복 곱셈을 이용해야 함.

using mat = vector<vector<ll>>;
mat mul(mat &a, mat &b){
    mat ret(2, vector<ll>(2, 0));
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                ret[i][j] += (a[i][k] * b[k][j]);
            }
            ret[i][j] %= MOD;
        }
    }
    return ret;
}

행렬 곱셈

#11442 홀수번째 피보나치 수의 합 [G2]

$F_{n} = F_{n-1} + F_{n-2} (n\ge2)$
계산은 위의 #11778 피보나치 수와 최대공약수와 동일하게 하면 됨

#1939 중량 제한 [G4]

DSU(서로소 집합, 유니온 파인드)문제.

int dsu[100001];
void init(int MAX){for(int i=0;i<=MAX;i++) dsu[i]=i;}
int find(int u) {
    return dsu[u] == u ? u : (dsu[u] = find(dsu[u]));
}
void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u != v) dsu[v] = u;
}

시작 -> 도착까지 얼마나 많이 운반할 수 있냐(옮길 수 있는 물품의 중량의 최댓값)

공장이 위치해 있는 섬의 번호를 st, ed라 하면

중량 제한을 내림차순으로 정렬
중량 제한이 큰 아이들부터 연결해서 st와 ed가 연결이 되면(find(st)==find(ed)) 그때의 중량 제한을 출력

가장 무거운 길을 다 걷다가 다 연결이 되면 그 길들의 가장 낮은 중량 제한이 제일 많이 운반할 수 있는 무게의 최대(정답)
내가 옳게 말하는게 맞나… @.@

#4195 친구 네트워크 [G2]

이름 매핑이라 map을 사용
1
map<string, string> dsu;

string``인s1와s2`입력 받으면서
아직 맵(dsu)에 없으면 추가하고
s1와 s2가 같은애를 가지고 있지 않으면 친구 수 더하고 merge

#16174 점프왕 쩰리 (Large)

BFS, queue쓰는 문제
그냥 queue<pair<int, int>>에 x, y좌표 넣고 BFS돌리면 됨

1 2	int dx[] = {1, 0}; int dy[] = {0, 1};

방향은 쉽게 쓰기 위해서 두고 for문으로 돌리기

for(int k=0; k<2; k++){
    int nx = x + dx[k]*w;
    int ny = y + dy[k]*w;
    // Do something
}

이런식으로 하니깐 편하더라.
그 외 해야할 조건

nx, ny가 범위 밖인지
이미 도착했는지

그외..

HaruHaru

귀엽다! ヾ(≧▽≦*)o

2022/01/05 수요일

#1965 상자넣기 [S2]

int dp[1009];
fill(dp, dp+N, 1);
int ans = dp[0];
for(int i=1; i<N; i++){
    for(int j=0; j<i; j++){
        if(a[j]<a[i]) dp[i] = max(dp[i], dp[j]+1);
    }
    ans = max(ans, dp[i]);
}

dp[k]: k번째까지의 제일 큰 상자 개수
대충 코드보면 기억할거야 하루야…

#1750 서로소의 개수 [G2]

for(int idx=1; idx<N; idx++){
    for(ll k=1; k<=100000; k++){
        dp[idx][k] += dp[idx-1][k];
        dp[idx][gcd(a[idx], k)] += dp[idx-1][k];
    }
}
cout << dp[N-1][1];

dp[idx][k]: 0~idx까지에서 gcd가 k가 되게 하는 원소들로 이루어진 집합의 개수
초기조건 dp[i][a[i]] = 1

2022/01/06 목요일

#4358 생태학 [S1]

1 2	cout << fixed; cout.precision(4);

소숫점 4번째 까지 표시하는 것

#18513 셈터 [G5]

샘터의 위치를 기준으로 해서
양 옆으로 쭉쭉 뻗어가며(BFS)
거리만큼 불행도를 더하면 된다
이미 집을 지었는지 파악하려면 set을 활용

for(int k=0; k<2; k++){
    int next = now + dx[k];
    if(s.count(next)) continue;
    // Do something
}

#21557 불꽃놀이 [S5]

양 끝 폭죽 더미를 제외한 폭죽 더미를 하나 고릅니다.
더미의 폭죽을 모두 터뜨립니다.
폭발한 폭죽 더미는 사라지고, 양 옆으로 가장 가까운 폭죽 더미의 높이가 1씩 감소합니다.

남은 두 폭죽더미의 높이 중 더 큰 값을 최소화해야 한다.
a[1]~a[N]이 있다면 a[2]~a[N-1]은 어차피 다 사라질 것
만약 a[1]이랑 a[N]중에서 a[1]이 더 높다면 a[2]를 터트려서 높이를 낮게 만든다

#1174 줄어드는 수 [S1]

int a[] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
for(int i=1; i<1024; i++){
    ll num = 0;
    for(int k=0; k<10; k++){
        if(i & (1<<k)) num = num*10 + a[k];
    }
    v.push_back(num);
}

비트마스킹?
1, 10, 11, 100, ..., 1111111111으로 하면 9, 8, 98, 87, 987, ..., 9876543210이 나오고 이것을 정렬해서 사용하면 된다.

#5376 소수를 분수로 [S1]

$a.bc\dot{d}e\dot{f} =\frac{abcd - abc}{10^5-10^3}$을 구현하면 된다.

#17425 약수의 합 [G5]

for(int i=1; i<=MAX; i++){
    for(int j=1; i*j<=MAX; j++){
        f[i*j] += i;
    }
}

자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다.

1
2
3

for(int i=1; i<=MAX; i++) {
    g[i] = g[i-1] + f[i];
}

x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다

문제가 요구하는 것과 같이 구현하면 된다

#4355 서로소 [G1]

ll phi(ll N){
	ll ans=N;
	for(ll i=2; i*i<=N; i++){
		if(N%i==0){
			ans -= ans/i;
			while(N%i==0) N/=i;
		}
	}
	if(N>1) ans -= ans/N;
	return ans;
}

참고 문헌: rkm0959님 블로그
오일러 파이 함수를 이용하면 된다.

#13076 Distinct rational numbers [G2]

$0\le a \le b \le N$인 기약분수 $a/b$를 구하는 문제
오일러 파이 함수를 이용
누적합을 사용

후기

Union-Find 어렵다. 좀만 꼬여도 잘 못할 것 같다.
DP 어렵다. 범위를 잘 못잡겠다.
계절학기 너무 싫다 사람살려

# PS # solved.ac # Daily BOJ