CodeDrive

문제:

페르마의 마지막 정리는, a, b, c가 0이 아닌 정수이고, n이 2보다 큰 자연수 일 때, an = bn + cn을 만족하는 자연수 a, b, c가 존재하지 않는다는 정리이다. 이 정리는 아직 증명되지 않았다.

하지만, 완전 세제곱 방정식 a3 = b3 + c3 + d3을 만족하는 1보다 큰 자연수를 찾는 것은 어렵지 않다. (123 = 63 + 83 + 103)

이러한 완전 세제곱 방정식과 a ≤ 100을 만족하는 {a, b, c, d}쌍을 모두 찾는 프로그램을 작성하시오.

입력:

이 문제는 입력이 없다.

출력:

a값이 증가하는 순서대로 아래 출력 형식과 같이 출력한다. b, c, d도 증가하는 순서로 이루어져야 한다. a값에 해당하는 b, c, d쌍이 여러 개 존재할 수 있다. 이때는 b 값이 작은 것부터 먼저 출력한다.

아래 출력 예제는 일부분만 나와있다.

풀이방법:

 조건이 맞는 a,b,c,d를 찾는 것은 쉬우나 시간을 줄이는 것이 이 문제의 핵심이다. a 같은 경우에는 6이 가장 같은 경우의 수 이기 때문에 6부터 시작하게 한다. 그리고 1보다 큰 자연수여야 하기 때문에 b는 2부터, b<c<d를 만족해야하기 때문에 c는 b부터, d는 c부터 시작하게 하도록 한다.

문제링크:

https://www.acmicpc.net/problem/4690

문제:

서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받는 학생이 구금되어있다.

그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2,4,6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있으면 연다. k번째 라운드에서는 번호가 k인 배수인 방이 열려 있으면 잠그고, 잠겨 있으면 연다. 이렇게 n번째 라운드까지 진행한 이후, 상범이는 위스키의 마지막 병을 마시고 쓰러져 잠든다.

입력:

입력의 첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄에 한 개씩 방의 개수 n(5<=n<=100)이 주어진다.

출력:

한 줄에 한 개씩 각 테스트 케이스의 답, 즉 몇 명이 탈출할 수 있는지를 출력한다.

풀이방법:

다이나믹 프로그래밍으로 풀어야 한다고 하는데 방의 개수가 100으로 작은편이기 때문에 완전탐색을 사용해서 풀었다.

0이면 열려 있고, 1이면 닫혀 있다고 했을 때, 해당하는 숫자 j의 배수마다 0이면 1로, 1이면 0으로 바꾸도록 했다. 이렇게 모두 탐색을 완료하면 0의 갯수에서 하나를 빼서 답을 구한다.

(다 풀고나니 1을 열려 있고, 0을 닫혀 있다 가정하고, 마지막에 sum을 하는 것이 더 깔끔할 것 같다.)

문제링크:

https://www.acmicpc.net/problem/6359

문제:

풀이 방법:

문제:

Leo는 집으로 돌아와서 아까 본 카펫의 빨간색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 빨간색 격자의 수 red가 매개변수로 주어질 때 카펫의 가로,세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

풀이 방법:

문제:

풀이 방법:

문제:

풀이 방법:

문제:

풀이 방법: