페어 프로그래밍이 현실적으로 어렵다는 팀원들의 전체적인 의견을 따라 각자 풀고 리뷰해 주기로 결정,
java 백준 2839 설탕 배달 https://www.acmicpc.net/problem/2839
2839번: 설탕 배달
상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그
www.acmicpc.net
java 언어로 문제를 풀려고 앉은 나는 그냥 greedy 하게 5kg 설탕봉지가 많은 경우부터 탐색해서 n kg을 만들기를 성공하면 바로 return해야겠다는 생각이 들었는데, 과거의 나의 풀이가 심상치 않다.
[4달전 cpp 풀이]
#include <string>
#include <iostream>
#include <sstream>
using namespace std;
int main(){
int n;
cin >> n;
//3kg와 5kg를 만드는 가장 최소의 봉지수는 1
//따라서 dp[3]과 dp[5]는 무조건 1
int *dp = new int[n+1]{-1};
dp[3] = dp[5] = 1;
//3과 5 다음인 6부터 for loop 순회
for (int i = 6; i <= n; i++) {
if (dp[i - 3]) dp[i] = dp[i - 3] + 1;
//이미 dp[i-3]에 값이 존재할때 dp[i]가 업데이트 됐었을 수 있다.
//만약 dp[i]에 값이 없다면 dp[i] = dp[i-5] +1 로 업데이트
if (dp[i - 5]) dp[i] = dp[i] ? min(dp[i] , dp[i - 5] + 1) : dp[i - 5] + 1;
}
cout << (dp[n] == 0 ? -1 : dp[n]) << endl;
return 0;
}
다이나믹 프로그래밍으로 이 문제를 풀려고 하다니.. 논리는 그래도 봐줄 만 하긴 한데, 홍대병 걸린 코드 같다.
**** java 코드에서 등장하는 scan 인스턴스는 BufferedReader와 StringTokenizer를 적절히 활용해서 새로 만든 입출력 담당 클래스의 인스턴스이며 print() 메서드는 이를 활용한 겁니다. 문제와 관련 없어 첨부하지 않음*
[현재 java 풀이]
static void input(){
int n = scan.nextInt();
// 가능한 5 봉지의 개수는 n/5개
int maxPack5 = n/5;
for(int i = maxPack5; i >=0 ; i--){
int remain = n - (i * 5);
if(remain % 3 == 0){
int pack3 = remain/3;
System.out.println(i + pack3);
return;
}
}
System.out.println(-1);
}
오히려 이쪽이 더 빠르고 간결하고 가독성이 좋은 풀이 같다. 한창 dp 풀 때라서 신나게 풀었을 수도,,
만약 문제가 모든 무게에 대해서 가능한지 여부와 가능한 최소의 설탕 봉지 개수를 원했다면 dp로 풀어야 하긴 할 것 같다.
java 백준 4948 베르트랑 공준 https://www.acmicpc.net/problem/4948
4948번: 베르트랑 공준
베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼
www.acmicpc.net
소수 찾기 유형의 문제인데, 문제를 읽어보면 알겠지만 각 테스트 케이스마다 각각의 답을 출력해야 하는 문제로, 테스트 케이스가 최대 몇 갠지 알려줬어야 하지 않나 하는 생각…
왜냐면 테케가 아주 많은 경우의 수를 생각하지 못하고 아래처럼 풀었다가 시간초과가 났다.
//에라토스테네스의 체
//넓은 범위의 수 중 소수가 몇개인지 - > 에라토스테네스의 체
for(int i= 2 ; i < n; i++){
if(n % i == 0)
return false;
// [0,0,2,3,0,5,0,7,0,0,0,11,
// 100000
static int sieveOfEratosthenes(int n){
int[] arr =new int[n];
for(int i = 0 ; i < n;i++){
arr[i] = i+n+1;
}
// arr 0 1 2 3 4 5
// 100001 100002
//제곱근 까지만
double root = Math.pow((n * 2), 0.5);
for(int i = 0 ; i < n ; i++) // *n
for(int divisor = 2 ; divisor <= root; divisor++) // * root n
if(arr[i] % divisor == 0)
arr[i] = 0;
int primeCount = 0;
for(int i = 0; i < n ; i++)
if(arr[i] > 0) primeCount ++;
return primeCount;
}
static void input() throws Exception{
int n;
while(true){
n = scan.nextInt();
if(n==0)
break;
sb.append(sieveOfEratosthenes(n) + "\\n");
}
print();
}
1 ≤ n ≤123,456 에 대하여 아래와 같은 극한의 테스트 케이스가 있을 수도 있고,
123,456
123,456
123,456
123,456
123,456
123,456
123,456
123,456
123,456
123,456
123,456
123,456
0
$$n\sqrt n $$ 의 시간복잡도의 코드를 n = 100000으로 돌리면 1억 회의 연산이 필요한데,
테스트케이스가 20개만 있어도 시간초과가 날 것이 뻔했다.
따라서 어차피 변하지 않을 소수 리스트를 문제가 요구하는 최대 범위까지 미리 구해놓고
요구하는 범위에 대해서 소수를 카운트해서 출력하기로 함
그리고, 2,3,5,7 등의 소수가 2,3,5,7로 나누어지기 때문에 소수가 아닌 것으로 잘못 분류되는 오류가 있어 나누는 수와 피연산자가 같지는 않은데 나누어 떨어지는 경우 소수로 분류하는 것으로 수정했다.
static void input() throws Exception{
//원래 소수인지 파악할때는 어떤 수의 제곱근까지만 나누어떨어지는지 검사해보면 된다.
// 에라토스테네스의 체 구현
int maxLen = 123456 * 2 + 1;
int[] arr =new int[maxLen];
for(int i = 1 ; i < maxLen;i++){
arr[i] = i;
}
double root = Math.pow(maxLen, 0.5);
for(int i = 0 ; i < maxLen ; i++)
for(int divisor = 2 ; divisor <= root; divisor++)
if(arr[i] != divisor && arr[i] % divisor == 0)
arr[i] = 0;
int n = -1;
while(true){
int primeCount = 0;
n= scan.nextInt();
if(n==0)
break;
for(int i = n+1; i <= 2*n ; i++)
if(arr[i] > 0) primeCount ++;
sb.append(primeCount + "\\n");
}
print();
}
java 백준 2869 달팽이는 올라가고 싶다 https://www.acmicpc.net/problem/2869
2869번: 달팽이는 올라가고 싶다
첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000)
www.acmicpc.net
그냥 수학문제,
v=100, a=7, b=3 일 때는
하루에 4씩 이동한다고 계산했을 때, 언젠가 96미터에서 낮을 맞이하면 등반 완료이다.
오늘 92미터에서 출발한다면, 낮에 99, 밤에 96이 되며, 이때 96미터가 되었으므로 하루 더 지나면 등반할 것을 안다.
그러므로 등반 기준선 96에서, 하루 이동 길이 4를 나눈 몫에다가 (낮이 되어야 등반 완료가 되므로) 하루를 더하면 되는데,
조심해야 할 점이 있다.
예를 들어 v=104인 a = 7, b= 3인 경우를 생각해 보면 97미터에서 하루 더 지나면 97 + 7 = 104가 되어 등반에 성공할 것이다. 그런데 a=7, b=3 스펙으로 정확히 97미터가 될 순 없고 96미터 다음은 100미터 이므로
달팽이의 현재 위치가 97미터가 되는 것과 100미터가 되는 것을 같게 봐야 한다는 것을 알 수 있다.
다음 날 등반이 완료되는 높이가 97,98,99,100인 경우 등반 완료 까지는 25 + 1 일 이 걸릴 것을 알 수 있는데, 여기서 97,98,99는 a-b인 4로 나누었을 때 몫이 24, 100은 몫이 25가 되므로 둘을 같게 해 줄 방법이 필요한데, 바로 a-b로 나눌 때 나머지가 존재하는 경우 +1을 하는 방식으로 해결할 수 있었다.
static void input(){
int up = scan.nextInt();
int down = scan.nextInt();
int v = scan.nextInt();
// 100미터인 상황 가정
// 7미터 올라가고 3미터 내려간다면, 매일 4미터 전진하는 것과 같다.
// 따라서 오늘92, 낮 99 밤 96 내일 낮 103 일 때 멈춰야 하는데,
// 다음 날 등반이 완료되는 높이를 구하자
// number + up >= v 일때 다음 날 등반 완료
int diff = up - down;
// 등반 성공 커트라인
int success = v - up; // 100 - 7 = 93
// 92 x (93, 94, 95), 96
int days = (success / diff) + (success % diff > 0 ? 1 : 0) +1;
System.out.println(days);
}
