서의 공간

[문제]: 17626번: Four Squares (acmicpc.net) 예를 하나 가지고 하나하나 따져보자. 첫 for문은 제곱수는 1개의 제곱수로 표현할 수 있으므로 그 부분을 처리한 것이고, 핵심은 2번째 for문이다. 먼저 dp[n]의 정의다. \[dp[n]=\text{제곱수들의 합이 \(n\)인, 제곱수들의 최소 개수}\] 즉, \(1=1^2\text{ 이므로 } dp[1] = 1,\) \(5=1^2+2^2\text{ 이므로 } dp[5] = 2,\) \(13=2^2+2^2+2^2+1^1\text{ 이긴 하지만, } 13=2^2+3^2\text{ 이기도 하다. 최소 개수이어야 하므로 }dp[13] = 2,\) \(60=1^2+1^2+3^2+7^2\text{ 이므로 } dp[60] = 4\) 이다..

[문제]: 9625번: BABBA (acmicpc.net) A와 B의 개수를 세기 위해 pair타입을 이용했다. pair 타입은 (A의 개수, B의 개수) 형식이다. 문자열을 본다면 스위치를 k번 눌렀을 때 문자열은 항상 (k-1번 문자열 + k-2번 문자열)이다. 식으로 표현하면, \[strPush(k) = strPush(k-1)+strPush(k-2)\] (예) 스위치를 5번 누른 문자열 = "BABBABAB" 스위치를 4번 누른 문자열 = "BABBA" 스위치를 3번 누른 문자열 = "BAB" 여기서 오해하지 말아야 할 것은 + 연산이 실제로 더하기를 의미하는 것은 아니고 문자열의 concatenate, 즉 문자열을 연결하는 연산이다. 실제 문제는 문자열이 아닌 A와 B의 개수를 구하는 것이기 때문..

[깃허브]: Seoui/study-on-baekjoon: 백준 온라인 문제 풀이 코드입니다 (github.com)