2024.02.19. ~ 2024.02.25.

백준 13 문제.

 

1. BOJ 31430 : A+B - 투 스텝 - B1

A + B가 최대 2*10^18까지 가능하다.

그런데 'a' = 0, 'b' = 1, ... 이렇게 매핑하면 26진법으로 표현이 되면서도 26^13 이 2*10^18보다 더 크므로 26진법 인코딩을 해주면 된다.

이후에 다음 프로그램 에서는 26진법 표현을 받고 이를 다시 10진법으로 변환하면 된다.

처음으로 푼 투 스텝 문제라서 리뷰해보았다. 투 스텝 문제를 이해하고 입문하기 매우 좋은 문제라 생각한다.

 

2.  BOJ 15651 : N과 M (3) - S3

Backtracking 문제다.

그냥 N^M 가지의 경우의 수를 전부 돌려보면 된다.

다른 N과 M 문제들과 비슷한 문제였다.

 

3. BOJ 5347 : LCM - S5

Number Theory 문제.

그냥 LCM을 계산해주면 된다. (a*b) / __gcd(a,b);

 

4. BOJ 1280 : 나무 심기 - P4

Segment Tree 문제.

좌표 x에 대해서 좌표 x보다 작은 좌표들에 심겨진 나무들을 l개 있고, 반대로 좌표 x보다 큰 좌표에 심겨진 나무들이 n-r개가 있다고 하자.

또한 좌표 x보다 작은 좌표에 심겨진 나무들의 좌표들을 x1,x2,...,xl 이라 하고, 좌표 x보다 큰 좌표에 심겨진 나무들의 좌표들을 xr, ... , xn이라고 하자.

그렇다면 좌표 x에 나무를 심으면 cost는 (xr+...+xn - (n-r)*x) + (l * x - (x1+x2+...+xl))로 계산할 수 있다.

따라서 Segment Tree에 [l,r] 범위에 대해서 각각 {나무의 개수, 나무 좌표값들의 합}를 저장하여 관리한다면 쉽게 답을 구할 수 있다.

 

5. BOJ 1244 : 스위치 켜고 끄기 - S4

Implementation + Simulation 문제.

남학생 쿼리에 대해서는 그냥 O(N)으로 구현해도 상관없다.

여학생 쿼리는 투 포인터로 구현하긴 했지만 N이랑 쿼리 수가 너무 작은 관계로, 그냥 O(N^2)로 구현해도 될 것 같다.

 

6. BOJ 1024 : 수열의 합 - S2

Math 문제.

연속된 범위의 수들의 개수가 홀수 개수라면 (중앙값) * (개수)가 N과 같으면 그 부분이 가능한거고,

짝수 개수라면 (중앙의 두 값의 합) * (개수/2)가 N과 같으면 그 부분이 가능하다.

따라서, L부터 100까지 모든 길이에 대해서 길이가 홀수면 N을 나눌 수 있는지 확인하고, 짝수면 2*N을 나눌 수 있는지를 확인하면 된다.

가능하다면 그 값들을 중심으로 나머지 수들을 채워나가면 되는데, 이건 또 수식으로 잘 정리하면 된다.

 

7. BOJ 15900 : 나무 탈출 - S1

BFS 문제.

이게 중간에 트리에서 특정 노드를 골라서 전체를 옮기는 문제면 몰라도...

어차피 한 턴에 말 하나를 부모 노드로 꼭 옮긴다면, 게임은 모든 리프 노드에 대해서 루트까지의 길이의 합만큼의 턴이 지나면 게임이 끝난다.

따라서 BFS를 활용해서 리프 노드 및 거리들을 파악해 이를 더하면 답을 찾을 수 있다.

 

이외에도 Bronze 6 문제를 풀었다.

이번 주 일지는 여기서 끝.