링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqPrpnKSCQDFAT_문제경로에서 등장하는 모든 숫자의 곱에서 맨 뒷자리에 연속으로 있는 0의 개수, 즉 trailing zero의 개수의 최소를 구하는 문제입니다.trailing zero가 나오기는 위해서는 10의 배수라는 의미이고, 소인수 중 2와 5의 개수 중 작은 쪽만 확인하면 됩니다.이 부분은 BOJ 1676 - 팩토리얼 0의 개수 문제에서 풀어보시면 됩니다.가장 왼쪽 위 (1, 1) 지점에서 시작해서 오른쪽 또는 아래쪽으로만 이동한다는 점은,다음 지점의 입장에서는 위쪽 또는 왼쪽의 영향만 받는다는 의미이기도 하지요.항상 위쪽 또는 왼쪽까지 도착..

링크: https://www.acmicpc.net/problem/5535문제각 날짜마다 입을 수 있는 옷들이 있고, 다음 날과 옷의 화려함의 차이가 최대한 크도록 옷을 고르는 문제이다.날짜마다 가능한 옷을 저장해둔다. 그 날에 한해서는 옷의 종류나 순서가 중요치않길래 화려함 정도를 넣어버렸다. 이제 각 날짜마다 옷을 하나씩 고른다면, 총 D일동안 N가지의 옷을 고르므로 경우의 수는 \(O(N^{D})\) 이다. 어떤 d번째 날에 A라는 옷을 골랐다고 치자. 그럼 d+1번째 날 이후로는 d번째 날에 A를 고른 영향이 계속 생긴다.즉, d번째 날에 a를 고른 이후로는 하나의 부분 문제로 볼 수 있다. 점화식을 dp[D][N] = D번째 날에 N번째 옷을 선택했을 때의 화려함의 최대값 으로 세우면 \(O(ND..

링크: https://www.acmicpc.net/problem/1308문제풀이 재활훈련을 시작했다.문제를 푸는 데 실수가 너무 많아진다..문제날짜, 시간 차이를 구하는 문제는 정수 하나로 변환해서 퉁 치는게 제일 편하다. (년/월/일 -> 총 X일)단, 조건 중에 천년을 넘어가면 gg를 출력해야하는데, 2000/05/05 ~ 2100/04/30 같은 경우는 천년을 넘기지 않음에 조심해야한다.코드

링크: https://www.acmicpc.net/problem/17520풀이균형잡힌 문자열에서 확인하는 모든 부분 문자열은 첫번째 문자를 포함한다. 즉, 앞에서부터 순차적으로 확인하여 0와 1의 개수가 1 이상 차이가 난다면 균형잡힌 문자열이 아니라는 뜻이다. 우선 무식하게 모든 경우의 수를 다 확인해볼 수 있다. i번째 위치를 0 또는 1로 결정하면서, 균형잡힌 문자열이 되는 경우만 탐색했다. n=3일 때, 010, 011, 100, 101 네 개의 문자열이 나온다. n=1부터 하나씩 확인해보면 \(2, 2, 4, 4, 8, 8, \dots, 2^{n-1}, 2^{n-1}, 2^{n}, 2^{n}\) 로 규칙성이 보인다. 이제 문제는 \(f(n)=2^{\lfloor{(n+1)}/2\rfloor}~mo..

링크: https://www.acmicpc.net/problem/1699문제주어진 N을 최소 몇 개의 제곱수의 합으로 표현할 수 있는 지 구하는 문제이다. 문제를 풀기 전에, 라그랑주 네 제곱수 정리를 알고 있으면 좋다. 백준 온라인 저지에 문제로도 등장했다. BOJ 3933 - 라그랑주의 네 제곱수 정리 요약하면, 모든 양의 정수가 많아야 4개의 제곱수의 합이라는 정리인데, 다시 말하면 이 문제의 정답은 최대 4라는 뜻이다. \(x^a + y^b + z^c + w^d = N\) 에서 \(a,~b,~c,~d\) 를 모두 확인해 볼 필요는 없다. 라그랑주의 정리에 의하면 모든 \(a,~b,~c\)를 찾았는 데 없으면 4개로 표현할 수 있기 때문이다. 즉, 3중첩 반복문으로 해결 가능하다.코드

링크: https://www.acmicpc.net/problem/17521문제보자마자 주식 문제가 생각났다.주식 문제들은 최대 이익을 내기 위해서 그리디하게 행동하면 된다. 값쌀 때 사서 값비쌀 때 팔면 된다.이 문제에서는 늘어난 코인만큼 다시 투자를 할 수 있으니, 상승 곡선이면 무조건 사는것이 이득이다. (늘어난 코인을 배로 불릴 수 있으니)코드 직관적으로 풀었지만 내심 불안했다.그래서 dp로도 풀어보았다. 물론, 같은 결과가 나왔고 정답이다.점화식은 dp[k] := k일까지 벌 수 있는 최대 코인이다.\(i < j\) 인 \(i\)일째에 가진 돈으로 전부 매수하고, \(j\)일에 모두 매도한다면 (두 날짜 사이의 변폭) * (i일에 살 수 있었던 코인의 수)만큼 벌 수 있을것이다.

https://www.acmicpc.net/problem/5612 문제 1분 단위로 터널에 들어간 차량의 수와 터널에서 나온 차량의 수가 주어졌을 때, 터널에는 차량이 최대 몇 대 있었는가? 풀이 처음에 터널에 있었던 차량 수에서, 매분 들어간 차량의 수를 더하고 나간 차량의 수를 빼면 된다. 중간에 한번이라도 터널 안 차량의 수가 음수가 되면 0을 출력하는 것에 주의하면 정답. 코드

[이전 블로그의 글] 각 노드에서 리프 노드까지의 거리가 (왼쪽으로 가든지, 오른쪽으로 가든지) 같도록 조정하는 것이므로 재귀를 생각할 수 있다. 이를 해결할 작은 문제로 재귀의 중간 과정부터 생각했다. 왼쪽과 오른쪽의 길이가 달라져서 조정이 필요한 상황은 "왼쪽 != 오른쪽" 이다. 이를 조정하는 작업은 더 작은 쪽에 가중치를 증가시키는 것이다. 가중치는 보정을 위해 추가하는 것이므로, 맞추고자 하는 차이만큼 증가시키면 된다. 코드 보기