#include<stdio.h>int num = 1; // 현재 막대기의 개수constint MAX = 64; // 처음 막대기의 길이int cur_smallest = MAX; // 현재 가장 짧은 막대기의 길이// 막대기 총 개수 반환intre_cut(int answer, int min){ // 찾는 막대기의 길이와 현재 가장 짧은 막대기의 길이 입력if (answer == MAX) {return num;}
num++; // 막대기를 자름
min /= 2;
if (min == answer) { // 내가 찾는 막대기의 길이와 현재 가장 짧은 막대기의 길이가 같으면
num--; // 직전에 막대기를 잘랐으니 같은 길이의 막대기가 하나 더 있음 -> 버리기return num; // 막대기 개수 반환
}
elseif (min > answer) // 내가 찾는 막대기의 길이보다 현재 가장 짧은 막대기의 길이가 더 길면
{
num--; // 직전에 자른 막대기 버리기returnre_cut(answer, min); // 찾는 답과 반으로 짧아진 가장 짧은 막대기의 길이 입력
}
else { // 내가 찾는 막대기의 길이보다 현재 가장 짧은 막대기의 길이가 짧으면returnre_cut(answer-min, min); // 내가 찾는 길이에서 현재 가장 짧은 막대기 길이 뺀 길이 입력
}
}
intmain(void){
int answer;
scanf("%d", &answer);
int number = re_cut(answer, cur_smallest);
printf("%d\n", number);
return0;
}
개선사항
재귀함수를 만들어서 써보는 건 처음이었는데, 역시나 계획 없이 무작정 짰다! 재귀 함수 쓸 때 아이디어를 먼저 떠올리고, 증명으로 검토한 후에 코드를 짜는 것이 더 안전할 것 같다. 사실 시도는 했으나 어떤 걸 증명의 대상으로 둬야 할 지 어려움이 있었다. 재귀 함수를 더 써보면서 무엇을 증명해야 할지 염두에 두는 것이 좋겠다.
#include<stdio.h>#include<stdbool.h>#include<stdlib.h>#include<string.h>voidset_zero(int* array, int array_len){ // 배열의 모든 원소를 0으로 초기화for (int i=0; i<array_len; i++) { array[i]=0; }
}
char** friend_name(char* names, char* giveTake[]){ // 문자열에서 친구의 이름을 구한다.char* give = NULL;
char* take = NULL;
give = strtok(names, " ");
take = strtok(NULL, " ");
giveTake[0] = give; // 선물을 준 친구
giveTake[1] = take; // 선물을 받은 친구return giveTake;
}
intsolution(constchar* friends[], size_t friends_len, char* gifts[], size_t gifts_len){
int answer = 0;
int i, j, k;
char* giveTake[2]; // 문자열에서 구한 친구의 이름을 넣을 함수int give_take[friends_len][friends_len]; // 한 친구가 특정 친구에게 준 선물의 개수int expectation[friends_len]; // 다음 달에 받게 될 선물의 개수int given[friends_len]; // 이번 달에 준 선물의 개수int taken[friends_len]; // 이번 달에 받은 선물의 개수// 배열을 0으로 초기화for (i=0;i<friends_len;i++) {set_zero(give_take[i], friends_len);}
set_zero(expectation, friends_len);
set_zero(given, friends_len);
set_zero(taken, friends_len);
for (i=0; i<gifts_len; i++) {
char** name;
name = friend_name(gifts[i], giveTake);
for(j=0; j<friends; j++) { int cmp = strcmp(name[0], friends[j]); if (!cmp){break;} }
for(k=0; k<friends; k++) { int cmp = strcmp(name[1], friends[k]); if (!cmp){break;} }
give_take[j][k]++;
given[j]++; // j번째 친구는 선물을 주었다.
taken[k]++; // k번째 친구는 선물을 받았다.
}
for (i=0; i<friends_len; i++) {
for (j=i+1; j<friends_len; j++) {
int dif = give_take[i][j] - give_take[j][i]; // 서로에게 준 선물 개수의 차이if (dif > 0) {expectation[i]++;} // i번째 친구가 선물을 더 많이 준 경우elseif (dif < 0) {expectation[j]++;} // j번째 친구가 선물을 더 많이 준 경우else { // 준 선물의 개수가 같은 경우int friend1 = given[i] - taken[i]; // i 번째 친구의 선물 지수int friend2 = given[j] - taken[j]; // j 번째 친구의 선물 지수if (friend1 > friend2) { expectation[i]++; } // i 번째 친구의 선물 지수가 더 큰 경우elseif (friend1 < friend2) { expectation[j]++; } // j 번째 친구의 선물 지수가 더 큰 경우// 두 친구의 선물 지수가 같은 경우 다음 달 선물을 받는 친구가 없다.
}
}
}
answer = expectation[0]; // 다음 달 받을 선물의 개수가 가장 많은 친구for (i=1; i<friends_len; i++) {
printf("%d\n", expectation[i]);
if ( answer < expectation[i] ) { answer = expectation[i]; }
}
return answer;
}
문제 밑의 입출력 예시를 많이 참고해서 풀었다.
찾아본 개념/함수
문자를 기준으로 문자열 나누기: char * strtok(char * str, const char * delim); 동작: 첫 번째 호출에서, 첫 번째 파라미터에 분할할 문자열을 가리키는 포인터를 전달한다.(문자열 상수를 넣는 것은 좋지 않다) 이후 str 내에서 delim에 해당하는 문자를 찾는다. 문자를 찾으면 \0으로 치환한 후, 첫 번째 토큰의 주소값을 반환한다. 이후 같은 문자열을 분할하고 싶으면 첫 번째 인수에 NULL을 넣게 되는데, 그래야 마지막으로 탐색한 위치부터 분할을 시작한다.
예를 들어 다음 코드에서 첫 번째 출력값은 str 배열의 a의 주소값, 두 번째 출력값은 e의 주소값, 세 번째 출력값은 h의 주소값이다.
문자열 비교: int strcmp(const char* str1, const char* str2); 동작: 두 문자열을 한 문자씩 아스키값으로 비교한다. 두 문자열이 같으면 0이 반환된다. 두 문자열이 다르면, 처음으로 다른 값을 갖게되는 두 문자의 아스키값의 대소를 비교한다. str1의 아스키값이 더 크면 양수가, str2의 아스키값이 더 크면 음수가 반환된다.
개선사항
문제를 너무 계획없이 푸는 것 같긴 함! 대충이라도 전체적인 틀을 생각해보고 풀기. 안 그럼 더 오래걸리고 쉽게 실수하는 것 같다.
그리고 포인터 쓰는데 자꾸 실수 함..! char**형 넣어야 되는데 char*형 넣는 등등,, 배열이랑 포인터 사용에 유의하기
