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

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



새해를 맞이해…

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



2022/01/02 일요일

#16155 업힐과 가희 [S1]

링크

  • 조사하려는 구간에 해당하는 높이를 구하면 좌표 두개가 나오는데
  • 그 좌표의 기울기를 구하면 된다. 기울기를 구하는 공식 알면 그거 쓰면 됨.
  • 분수로 나타내야해서 gcd(a, b)를 이용하면 된다.
1
2
3
4
5
struct slide{
ll x, y;
};

slide a[60], ans;

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

#5430 AC [G5]

링크

  • 그냥 너무 정직하게 풀면 시간초과가 당신을 기다리게 된다.
    image
  • 지우고 돌리고 하는데 $O(N)$만큼 걸린다고 들었다.
  • 머리를 굴려야 한다!
1
2
3
4
5
6
7
8
9
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]

링크

1
2
3
4
5
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버전이라고 생각이 들었다.
1
2
3
4
5
6
7
8
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그림을 봤으니 이걸 가지고 거꾸로 올라가면 된다.
    DP Table

#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);

  • ss[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)$
  • nm1,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}$
  • 행렬 곱셈도 반띵반띵하는 분할정복 곱셈을 이용해야 함.
1
2
3
4
5
6
7
8
9
10
11
12
13
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]

링크

#1939 중량 제한 [G4]

링크

  • DSU(서로소 집합, 유니온 파인드)문제.
1
2
3
4
5
6
7
8
9
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라 하면

  1. 중량 제한을 내림차순으로 정렬
  2. 중량 제한이 큰 아이들부터 연결해서 sted가 연결이 되면(find(st)==find(ed)) 그때의 중량 제한을 출력
  • 가장 무거운 길을 다 걷다가 다 연결이 되면 그 길들의 가장 낮은 중량 제한이 제일 많이 운반할 수 있는 무게의 최대(정답)
  • 내가 옳게 말하는게 맞나… @.@

#4195 친구 네트워크 [G2]

링크

  • 이름 매핑이라 map을 사용
    1
    map<string, string> dsu;
  1. string``인s1s2`입력 받으면서
  2. 아직 맵(dsu)에 없으면 추가하고
  3. s1s2가 같은애를 가지고 있지 않으면 친구 수 더하고 merge

#16174 점프왕 쩰리 (Large)

링크

  • BFS, queue쓰는 문제
  • 그냥 queue<pair<int, int>>x, y좌표 넣고 BFS돌리면 됨
1
2
int dx[] = {1, 0};
int dy[] = {0, 1};

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

1
2
3
4
5
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]

링크

1
2
3
4
5
6
7
8
9
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]

링크

1
2
3
4
5
6
7
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까지에서 gcdk가 되게 하는 원소들로 이루어진 집합의 개수
  • 초기조건 dp[i][a[i]] = 1



2022/01/06 목요일

#4358 생태학 [S1]

링크

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

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

#18513 셈터 [G5]

링크

  • 샘터의 위치를 기준으로 해서
  • 양 옆으로 쭉쭉 뻗어가며(BFS)
  • 거리만큼 불행도를 더하면 된다
  • 이미 집을 지었는지 파악하려면 set을 활용
1
2
3
4
5
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]

링크

1
2
3
4
5
6
7
8
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]

링크

1
2
3
4
5
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]

링크

1
2
3
4
5
6
7
8
9
10
11
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;
}

#13076 Distinct rational numbers [G2]

링크

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


후기

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