궤도

문제 풀이 동적 계획법으로도 풀 수 있을 것 같은데 나는 재귀함수로 풀었다. 입력이 둘 다 1이상으로 들어온다고 하니, 굳이 0층의 사람까지 따질 필요는 없을 것 같다. 0층의 i호에는 i명이 산다고 하니, 1층의 i호에는 1+2+...+i명이 살 것이다. 그보다 높은 층에 대해서도 이 논리는 변하지 않으니 이대로 재귀함수를 짜면 된다. 소스코드 #include using namespace std; int live(int k, int n) { //재귀함수 int people = 0; if (k == 1) { for (int i = 1; i = 1; i--) people += live(k - 1, i); } return people; } int main() { int T, k, n; cin >> T; fo..

문제 풀이 최대한 5kg 봉투를 많이 가져가야 적은 수의 봉투를 가져가게 될 것이다. 그러니 일단 최대한 5kg 봉투에 담는다고 생각한다. 남은 kg수가 0이라면 그대로 루프를 끝내고 3이라면 3kg 봉투 하나 더해주고 끝내면 되지만, 그렇지 않은 경우가 있다. 그렇다면 5kg 봉투를 하나씩 풀면서 3으로 나누어 떨어지는지 확인해 본다. 소스코드 #include using namespace std; int main() { int N, remain, five, three; bool possible = false; cin >> N; five = N / 5; remain = N % 5; if (remain == 0 || remain == 3) { //0 or 3이면 바로 three = remain / 3; p..

문제 풀이 문제를 풀기 위해 문자열을 숫자화 했다. 간단하게 결과만 먼저 말하면, happy->01223 / new->123 / abab->0101로 숫자화 된다. 결과를 보면 알겠지만 그룹 단어라면 숫자화된 결과 값이 non-decreasing의 모습을 하고 있다. 이제 어떻게 이런 숫자가 나왔는지 설명하도록 하겠다. 각 알파벳을 숫자로 바꿀 flag 변수를 선언하고, 0으로 초기화 한다. 그리고 문자열을 처음부터 돌며 각 문자를 확인한다. 해당 문자가 등장한 적 없다면 현재의 flag 값으로 반영해주고 flag를 증가한다. 만약 읽었던 알파벳이라면 해당 알파벳에 어떤 flag값이 반영됐었는지에 대한 정보가 저장됐기 때문에 그냥 그걸 바로 가져오면 된다. 이렇게 문자열을 숫자로 바꿔서 non-decre..

문제 풀이 이 문제의 핵심은 두 가지 있다. 하나는 띄어쓰기를 포함해 입력을 받는 것이고, 다른 하나는 다양한 입력 경우의 수를 고려해 단어의 수를 세는 것이다. getline 함수를 이용하면 띄어쓰기를 포함해서 입력을 받을 수 있다. 다만 입력을 저장하는 변수의 자료형에 따라 사용법이 다르다. string str; getline(cin, str, '\n'); char c[1000]; cin.getline(c, 1000, '\n'); 마지막 인자로 들어간 '\n'는 생략할 수 있다. default 값으로 '\n'이 들어가고, 사용자가 원하는 값을 임의로 넣을 수도 있다. 'a'를 넣을 수도 있고, ' '를 넣을 수도 있다. 입력을 받았으니 단어의 수를 셀 차례이다. 공백이 연속으로 나오는 경우는 없다고 ..

문제 풀이 일단 알파벳의 등장 횟수를 체크해야하니 알파벳의 개수만큼의 크기를 가진 배열(alpha[26])을 만들어준다. 소문자 영어의 아스키코드는 97부터 시작하고 대문자 영어의 아스키코드는 65부터 시작한다. 소문자와 대문자를 구분하지 않으니 대소문자 여부를 판단해 적절히 alpha 배열에 넣어준다. 완성된 alpha 배열을 돌며 최대값을 찾아야 하는데, 그와 동시에 해당 최댓값에 해당하는 알파벳이 2개 이상인지도 체크해야 한다. 이를 위해 bool 변수 flag를 뒀다. 영어 대소문자 문제는 많으니까 각각의 아스키코드를 외워두는게 나쁘진 않을 것 같다. 소스코드 #include #include using namespace std; int main() { int alpha[26], max = 0, m..

문제 풀이 1,000 이하 라고는 하지만 1,000은 한수가 아니다. 그리고 1~99는 무조건 한수다. 그렇다면 세자리 수에 대해서만 한수여부 체크를 하면 된다. 세자리 수를 셋으로 쪼갠다. (part[0], part[1], part[2]) 그리고 (part[0]-part[1])==(part[1]-part[2]) 인지 확인하는데, 이거 말고 등차수열의 성질을 이용해서 2*part[1]==part[0]+part[2] 인지 확인해도 상관없다. 소스코드 #include using namespace std; bool isHan(int n) { int part[3]; if (n < 100) //100미만이면 무조건 한수 return true; else if (n == 1000) //1000은 안됨 return f..

문제 풀이 A가 B의 생성자가 되기 위해선 A

문제 풀이 이 문제를 풀 당시에는 이제 막 c++을 알아가던 단계였다. 그래서 저기 나오는 vector가 무엇인지 검색을 좀 해봐야 했다. 자료구조 할 때 배웠던 linked list와 비슷한 기능을 하는 것 같았는데 이 사실을 알고 너무 억울했다. 난 c로 하나하나 구현하느라 고생했는데 c++엔 이런 좋은게 있었다니! 나중에 알고보니 c++엔 스택, 큐, 덱 등등 내가 c로 개고생하면서 구현했던 모든 것들이 기본으로 있었다고 한다. 뭐 그 때 알고 있었다고 해도 c로 구현할 수 밖에 없었으니 어쩔 순 없지만 계산기의 존재를 모르고 손으로 계산하던 기분이었다. c++도 이렇게 좋은게 많은데 파이썬은 얼마나 더 좋을까? 하지만 파이썬은 너무 심플하게 생겨서 아직까지 낯을 가리고 있다. 소스코드 #inclu..