궤도

문제 풀이 커다란 체스판을 8x8 체스판으로 만들 수 있는 모든 경우의 수에 대해 계산한다. 체스판을 자르고, 편의상 왼쪽 맨위칸은 흰색으로 시작한다고 가정한다. 바꿔야 할 칸의 수를 계산했다면 이게 32보다 큰지 확인해야 한다. 만약 32칸보다 많이 바꿔야 한다면, 그냥 반대로 칠하는게 더 나았던 상황인 것이다. 아무튼 이런식으로 각 부분 체스판마다 바꿔야 하는 칸 수를 세고 최솟값을 갱신하면 된다. 소스코드 #include using namespace std; int main() { int N, M, i, j, a, b, fix, min_fix = 65; cin >> N >> M; char** panel = new char* [N]; for (i = 0; i < N; i++) panel[i] = ne..

문제 풀이 지금까지 봐온 별찍기 문제 중에서 가장 어려웠다. 바로 출력하는건 정말 어려울 것 같아서 배열을 만들었다. 재귀함수를 돌리며 배열에 적당히 값을 넣어주고 한번에 출력하면 될 것 같았다. 배열을 9등분 한다고 했을 때, 가운데를 제외한 모든 구역에 대해 재귀함수를 호출한다. 배열의 크기가 1x1이 되면 호출을 끝내면 될 것이다. 어차피 가운데에 대해서는 함수가 호출되지도 않을테니 바로 별을 넣어주면 된다. 재귀함수의 인자로는 뭐가 있으면 될까. 전체 배열, 부분 배열의 왼쪽 맨위 좌표, 부분 배열의 크기를 넣으면 된다. 소스코드 #include #include using namespace std; void star(char** matrix, int x, int y, int n) { if (n =..

문제 풀이 원의 내접과 외접에 대해 기억이 난다면 이 문제가 그리 어렵지 않을 것이고, 나처럼 기억이 가물가물 하다면 힘들 것이다. 각 좌표(x1, y1 / x2, y2)를 중심으로 하고 반지름이 (r1 / r2)인 원을 그려보자. 류재명이 존재할 수 있는 위치는 각각의 경우에 대해 해당 원의 경계선이다. 원을 2개 그리게 되니까 두 원의 교점의 수가 류재명이 있을 수 있는 좌표의 수다. 그렇다면 두 원의 관계는 어떤 경우가 있을까. 빨간원과 초록원은 조규현과 백승환의 위치가 같은 경우이다. 이 상황에서 두 원의 반지름이 다르면 류재명이 존재할 수 있는 위치는 없고, 같다면 무한하다. 검은원과 보라색원은 두 원의 교점이 1개인 경우다. 각각 내접, 외접하고 있다. 파란원은 교점의 수가 2개이고 주황색 원..

문제 풀이 에라토스테네스의 체를 이용해 소수를 구하는 문제다. 에라토스테네스의 체가 무엇이냐고 물어본다면... 이런식으로 특정 소수의 배수를 전부 지우는 과정을 통해 소수를 구하는 방법이다. 만약 1~n 사이의 소수를 구하고 싶다면 √n 까지만 구하면 된다. 왜일까? n보다 작거나 같은 합성수 m=ab가 있다고 하자. a와 b가 모두 최대일 때는 a=b=√n 일 때이다. a가 이보다 커지면 b가 √n보다 작아지고 반대의 경우엔 a가 √n보다 작아질 것이다. 그러므로 √n 까지만 체크해도 모든 합성수는 지워진다는 것이다. 그렇다면 이제 구현을 할 차례이다. 0과 1은 소수가 아니니 지워주고 2부터 시작한다. 2의 배수를 전부 지워주고, 3의 배수를 전부 지워주고, 4의 배수를 지울 필요는 없다. 왜냐하면 ..

문제 풀이 동적 계획법으로도 풀 수 있을 것 같은데 나는 재귀함수로 풀었다. 입력이 둘 다 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'를 넣을 수도 있고, ' '를 넣을 수도 있다. 입력을 받았으니 단어의 수를 셀 차례이다. 공백이 연속으로 나오는 경우는 없다고 ..