문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net dp[idx] = n -> idx까지의 최대 연속합이 n이라는 의미이다. dp[제곱수]는 무조건 1이다. 따라서 처음엔 어떤 수던간에 dp[i] = dp[직전 제곱수] + dp[i-직전 제곱수] 즉 dp[i] = 1 + dp[i-직전 제곱수] 라는 공식을 세우고 풀었는데 틀렸다. 코드는 다음과 같았다. #include #include #include #..
알고리즘
문제 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 처음에 문제를 보고 도통 어떻게 풀어야하는지 답이 안잡혔는데,, 질문 게시판을 잠깐 보고 아이디어를 얻어 바로 풀었다. 힌트는 다음과 같다. 뒤에 0이 붙는 개수를 구해야하는데, 0이 붙는다는 것은 10이 한번씩 곱해진다는 것이다. 10의 소인수는 2와 5인데, 보통 2는 5보다 소인수로 많이 가지므로, 곱해지는 5의 개수를 카운트하면 된다. #include #include #include #include #include #include #include #include #inc..
https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net #include #include #include #include #include #include #include #include #include #include #include using namespace std; //성공 string s; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); getline(cin, s); w..
문제 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 제한 메모리가 의도적으로 낮게 설정 되어있다. 처음엔 아무생각 없이 평소 하던대로 벡터에 입력 받고, sort함수로 정렬 후 출력했다. 당연히 결과는 메모리 초과. #include #include #include #include #include #include #include #include using namespace std; int n; vector v; int main() { ios_base::sync_w..
문제 https://www.acmicpc.net/problem/5635 5635번: 생일 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 #include #include #include #include #include #include #include #include #include #include using namespace std; int n, year, month, date; string name, youngest, oldest; vector nameVec; vector dateVec, monthVec; vector yearVec; //year, idx vector youngVec, oldVec,..
