Dev Diary.

www.acmicpc.net/problem/4796

이 문제를 처음보면 무슨말인지 이해가 잘 가지 않았다.

그래서 문제를 또읽고 읽어보니 어떻게 풀면 되겠구나 하는 포인트를 잡았다.

캠핑장은 20일 중 10일만 사용할 수 있다.

10일 사용 10일 미사용 (총20일) 이때 휴가는 28일 이니 8일을 더 쓸 수 있다.

총 18일 사용가능하다.

식으로 해보면 28/20*10 == V/P*L 만큼의 일수가 사용가능하고

28%20 = 8 만큼의 일수를 더 사용할 수 있다.

그렇게 코딩을 하였더니 문제가 생겼다.

나머지 값이 L값보다 큰 경우의 수를 놓쳤다.

5일만 사용가능, 연속하는 8일 휴가는 15일 이라고 생각해보자

15/8*5 = 5일

15%8 = 7일 

5+7 =12일? 

아니다!

5일사용 3일미사용 5일사용 3일미사용(16일) 이미 휴가 리미트를 넘어버린상황에서 10일을 사용가능하다.

삼항 연산자를 이용하여 나머지값보다 큰 경우 L값만 더해주는 식으로 코딩했다!

package test;

import java.util.Scanner;
public class test {

	public static void main(String[] args) {
	       Scanner sc = new Scanner(System.in);
	        
	       int testc = 1;
	       int L,P,V;
	       while(true) {
	    	  L = sc.nextInt();
	    	  P = sc.nextInt();
	    	  V = sc.nextInt();
	    	  
	    	  if(L==0&&P==0) {
	    		 break;
	    	  }
	    	  int ex = (V%P) > L ? L : V%P;
	          int day = (V / P)*L + ex;
	    	  System.out.println("Case "+testc+": "+ day);
	    	  testc++;
	       }
	        
	        
	}
}

www.acmicpc.net/problem/10162

이 문제를 보니 대표적인 그리디 문제라고 판단되어졌다. 많은 연습끝에 이 문제가 쉬워보였다.

결국 동전 대신 5분 1분 10초 가 있는것! 

1.입력 값은 초 단위니까 단위를 맞춰주기위해 5분을 300초로 1분을 60초로 변환 후 3칸짜리 배열에 넣어준다.

2. 각 버튼이 몇번 사용됬는지를 체크하기위해 배열을 하나 더 사용하였더니 쉬웠다!

package test;

import java.util.Scanner;
public class test {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int[] abc = new int[] {300,60,10};
        //초단위 변환 후 배열 초기화
		int[] tmp = new int[3];
        //횟수를 저장하기위한 배열
		int t = sc.nextInt();
		int na = t;
		
		for(int i=0;i<abc.length;i++) {
			if((na%abc[2])!=0) {
				System.out.println("-1");
				break;
                //10으로 나누었을때 나머지가 0이아니라면 나눠지지 않는다는 뜻이니까 -1
			}
			else {
				tmp[i] = na/abc[i];
                //몫=횟수를 저장
				na %= abc[i];
				System.out.print(tmp[i]+" ");
			}
		}
}
}

열심히 달려봅시다!!~

www.acmicpc.net/problem/2217

단순하게 생각했을때 쉽다고 생각되었다. N개의 로프중 최대중량이 가장 작은 로프가 항상 기준이 되어야한다

그렇지않으면 끊어지기 때문이다. 하지만

모든 로프를 사용해야할 필요는 없고, 임의로 몇 개의 로프를 골라서 사용해도 된다 라는 점을 생각해보았을때

1. N값을 입력받는다. N이 5이라면

2. 10, 15, 1, 18, 20 순으로 들어왔다고 치자

3. 모든 로프를 사용할 경우 1을 기준으로 5개의 로프는 5중량을 버틸 수 있다.

4. 위의 케이스는 극단적이지만 이 문제의 맹점이라고 생각한다. 이때 로프 1이 끼게 됨으로써 최대중량이 줄어들게된다 이 것을 구현하기 위해서는 내림차순으로 정렬을 한 후에 반복문을 통해 구할 수 있을거라 생각하고 구현해보겠습니당.net/problem/2217

2217번: 로프

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하

www.acmicpc.net



단순하게 생각했을때 쉽다고 생각되었다. N개의 로프중 최대중량이 가장 작은 로프가 항상 기준이 되어야한다

그렇지않으면 끊어지기 때문이다. 하지만

모든 로프를 사용해야할 필요는 없고, 임의로 몇 개의 로프를 골라서 사용해도 된다 라는 점을 생각해보았을때

1. N값을 입력받는다. N이 5이라면

2. 10, 15, 1, 18, 20 순으로 들어왔다고 치자

3. 모든 로프를 사용할 경우 1을 기준으로 5개의 로프는 5중량을 버틸 수 있다.

4. 위의 케이스는 극단적이지만 이 문제의 맹점이라고 생각한다. 이때 로프 1이 끼게 됨으로써 최대중량이 줄어들게된다 이 것을 구현하기 위해서는 내림차순으로 정렬을 한 후에 반복문을 통해 구할 수 있을거라 생각하고 구현해보겠습니당

package test;

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class test {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		Integer[] rope = new Integer[n];
		//로프의 중량을 담을 배열
		
		for(int i=0;i<5;i++) {
			rope[i]=sc.nextInt();
			//중량 입력
		}
		
		Arrays.sort(rope,Collections.reverseOrder());
		//내림차순 정렬
		int[] wei = new int[n];
		//최대중량을 담을 배열 선언
		int result = 0;
		//최대중량을 담을 변수
		
		for(int i=0;;i++) {
			
			if(i==0) {
				wei[i] = rope[i]; 
				//첫번째 바퀴때는 최대중량이 곧 로프의 최대중량이된다.
			}
			else {
				//두번째 바퀴부터
				if(wei[i-1] >  (rope[i]+rope[i+1])/(i+2)) {
					//만약 현재 최대중량보다 최대중량이 작다면
					result = wei[i-1];
					//result 변수에 현재 최대중량값을 저장한다.
					break;
				}
				else {
				wei[i] = (rope[i]+rope[i+1])/(i+2);
				//그렇지 않다면 최대중량을 저장한다.
			}
		}
		}
		System.out.println(result);

	}
}

단지 생각대로 적은 코드지만 돌아가지도 않고 뭔가 놓치고 있다 for에 else절이 이상한것 같다 다른 사람이 쓴 코드를 보며 내가 뭘 잘못했을까... 생각해봐야겟다

저녁밥을 먹으며 생각해보았다.

package test;

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
public class test {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		Integer[] rope = new Integer[n];
		//로프의 중량을 담을 배열
		
		for(int i=0;i<n;i++) {
			rope[i]=sc.nextInt();
			//중량 입력
		}
		
		Arrays.sort(rope,Collections.reverseOrder());
		//내림차순 정렬
		int max = 0;
		for(int i =0; i<n;i++) {
			if(max < rope[i] * (i+1)) {
				max =  rope[i] * (i+1);
			}
		}
		System.out.println(max);
}
}

차근차근 생각해보니 쉬운문제였다 

다른사람들의 코드는 오름차순으로 하는코드들을 봤는데 

내림차순으로 정렬하는것이 미세하게나마 빠르다고 생각한다. 최대값을 구하는 것이기때문에

최대값을 찾은 후 뒤에나오는 값들은 무조건 최대값이 아니기때문에 계산할 필요가 없어진다.

www.acmicpc.net/problem/1541

이 문제를 풀기위해 생각을 해보자 뭔가 처음보는 듯한 유형이다.

일차원적인 생각은 최소로 만들기위해서는 -뒤에 절대값이 최대한 크게 괄호로 묶어주면 될 것이라고 생각된다.

package test;

import java.util.Scanner;

public class test {

	public static void main(String[] args) {
		int sum = Integer.MAX_VALUE;
		Scanner sc =new Scanner(System.in);
		String[] n = sc.next().split("-");
		
		for(int i=0;i<n.length;i++) {
			int tmp = 0;
			
			String[] add = n[i].split("\\+");
			
			for(int j = 0; j < add.length; j++) {
				tmp += Integer.parseInt(add[j]);
			}
			
			if(sum == Integer.MAX_VALUE) {
				sum = tmp;
			}
			else {
				sum -= tmp;
			}
		}
		System.out.println(sum);
	}
}

어떻게 해야할지 감이 안잡혀 다른 사람들이 짠 코드를 참고하였다.

문자열에서 -가 나오고 다음 -가 나오기전까지의 +들은 -로 바뀐다 결국 -가 나오는 시점부터 뒤는 쭉 -값이다.

신박한 문제였다 나름 재미있었고 이런 문제가 다시 나온다면 혼자만의 힘으로 풀어봐야겠다.

www.acmicpc.net/problem/5585

이 문제를 위한 나의 해결법은

1. 500엔으로 나눈 몫 나머지를 구하고

2. 500엔으로 나눈 나머지를 100엔으로 위와 마찬가지로 구한다.

10엔 5엔 도 마찬가지로 구하고 1엔때의 몫을 구한다.

package test;

import java.util.Scanner;

public class test {

	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		int n = sc.nextInt();
		
		int coin[] = {500,100,50,10,5,1};
		int sum =0;
		int nam =1000-n;
		
		for(int i =0;i<6;i++) {
			sum += nam/coin[i];
			if(n%coin[i]!=0) {
				nam = nam%coin[i];
			}
			else {
				break;
			}
		}
		System.out.println(sum);
	}
}

이 문제를 보고 일단 coin 배열에 동전에 유형들을 넣고

for문을 이용하여 최대한 짧게 구현하였다. 문제를 잘못이해하여 1000엔을 주고 나머지를 구해야하는데 입력값 그대로를 나눠버려서 살짝 착오가 생겼지만 문제를 다시한번 읽어보니 nam값을 1000에서 초기값을 빼서 계산했다!

그랬더니 정답!!

다른사람들이 짠 코드를 보며 나와다른점이 무엇일까 생각해보기로했다!

www.acmicpc.net/problem/11047

이 문제를 보고 나의 해결법은

1. n만큼의 배열을 생성한다.

2. for문을 통해 n만큼의 배열에 값을 집어넣는다.

3. for문을 통해 n번째 부터 시작하여 n값이 감소하며 몫이 0보다 커질때를 구한다.

4. 몫이 0보다 크다면 나눌 수 있는 제일 큰값이라는 소리이므로 그 값을 몫 변수에 저장한다.

5. 이때 나오는 나머지 값을 이중 폴문을 이용하여 같은 방법으로 찾았다.

여기까지 했을때 1번 입력에 대한 정답은 구했지만 2번 입력에 대한 정답을 구하지 못했다.

package test;

import java.util.Scanner;

public class test {

	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int m =0;
		//n[i]로 나눌때의 몫
		int m2 =0;
		// n[j]로 나눌때의 몫
		int na =0;
		// n[i]로 나눌때의 나머지
		
		int num[] = new int[n];
		
		for(int i =0;i <n;i++) {
			num[i] = sc.nextInt();
		}
		
		for(int i =n-1; i>=0; i--) {
			if((k/num[i])>0) {
				//처음 가장 큰 수로 나눠질때의 경우
				m = k/num[i];
				// 몫을 저장 동전의 수의 일부
				na = k%num[i];
				// 나머지값 저장
				
				for(int j=i;j>=0;j--) {
					//이때의 i값부터 다시 탐색
					if(na/num[j]>0) {
						//다음 가장 큰 수로 나눠질 경우
						m2 = na/num[j];
						// 두번째 몫을 저장 
						break;
					}
				}
				break;
			}
		}
		System.out.println(m+m2);
	}
}

뭔가 이상함을 느꼇다.. 10원의 경우도 있어야 한다는걸 늦게 깨달았다. 그렇다면 1의자리수까지 표현하려면?

뭔가 프로그램이 복잡해 질 것 같다는 생각이 들고 다시 한번 처음으로 돌아가 생각해보기로 하였다.

나의 부족함을 느끼게 해주는 문제였다... 왜이래 멍청하지..

이중 for문 마저 쓸필요가 없고

1. num[i]가 처음으로 같거나 작을때 나눈 몫 값을 저장한다. 

2. 이때 k 값은 나머지값으로 변환시킨다.

3. 반복문이 돌고 몫 값에 몫 + 다음번의 몫 값을 더해준다.

이런식으로하면 for문안에서 몇줄만으로 해결이 되는 문제라는걸 알게되었다.....

package test;

import java.util.Scanner;

public class test {

	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int m = 0;
		
		int num[] = new int[n];
		
		for(int i =0;i <n;i++) {
			num[i] = sc.nextInt();
		}
		
		for(int i = n-1;i>=0;i--) {
			if(num[i] <= k) {
				m += (k/num[i]);
				k = k%num[i];
			}
		}
		System.out.println(m);
	}
}

매일매일 공부하면 좀더 발전할거라 믿고 열심히 해야겠다.

www.acmicpc.net/problem/11399

설탕 배달 문제 보다는 쉬워보였다.

1. n을 입력받는다.

2. n만큼의 배열을 생성한다.

3. for문을 통해 배열의 값을 넣어준다.

4. 정렬 알고리즘을 이용해 최소가 되게끔 오름차순 정렬한다.

5. 여기서 코드를 어떻게 짜야할지 생각하는 도중 첫번째 값은 n만큼 더해지고 두번째 값은 n-1만큼 더해진다는 규칙을 찾았다!

package test;

import java.util.Scanner;

public class test {

	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		int n = sc.nextInt();
		int time[] = new int[n];
		int tmp = 0;
		int nn = n;
		int sum =0;
		
		for(int i=0;i<n;i++) {
			time[i] = sc.nextInt();
		}
		sc.close();
		
		for(int i =0;i<n-1;i++) {
			for(int j =i+1; j<n;j++) {
				if(time[i]>time[j]) {
					tmp = time[i];
					time[i]=time[j];
					time[j]=tmp;
				}
			}
		}
		for(int i=0;i<n;i++) {
			sum += time[i]*nn;
			nn--;
		}
		System.out.println(sum);
	}
}

혼자만의 힘으로 짠 코드인데 일단 ...

정답을 맞추긴 했지만 구글링을통해 다른사람들의 코드를 보고 내 코드와 다른점이 무엇일까 궁금해졌다!

Array.sort() 를 쓰면 정렬을 해주는 라이브러리가 있었다.. 하지만 있다는 것만 알아두고 공부하는 단계에서는 쓰지 않는 것이 좋다고 생각된다! 프로그래밍 적 사고를 많이 해야 실력에 도움이 될것같기 때문..

www.acmicpc.net/problem/2839

처음 이문제를 보고 

1. N값을 5로 나눈값을 몫변수에 저장한다.

2. N값을 5로 나눈 나머지값은 나머지변수에 저장한다.

3. 나머지값을 3으로 나눈 값을 변수에 저장하고

4. 5로 나눈 몫변수와 나머지값을 3으로 나눈 값의 합을 저장한다.

5. 만약 5로 나눈 나머지변수가 3의 배수가 아니라면 -1을 출력한다.

6. 그렇지 않다면 5로나눈 몫변수와 나머지값을 3으로 나눈 값의 합을 출력한다.

package test;

import java.util.Scanner;

public class test {

	public static void main(String[] args) {
		System.out.println("몇 킬로 필요한가여 ? ");
		Scanner scanner =new Scanner(System.in);
		int n = scanner.nextInt();
		
		int five_quotient = n/5;
		int five_Remainder = n%5;
		int three_num = five_Remainder/3;
		
		int finaln = five_quotient+three_num;
		
		if(!(five_quotient%3==0)) {
			System.out.println("-1");
		}
		
		else {
			System.out.println(finaln);
		}
		
		
	}
}

내 생각에는 이렇게 하면 될줄 알았지만 N의 값이 3의배수일때 오류가 발생한다...

6을 입력했을때 바로 5로 나눠버려서 -1 값을 출력해버린다.

최소의 개수를 맞추기위해 5로나눈다는 생각이 짧았다!!!! 

또 다시도전했을때 11을 입력했을때 -1 값이 출력되었다.

5a+3b 형식의 경우도 있고 최소를 구해야 한다. 다시 처음으로 돌아가서 생각하기위해

구글링..!

구글링을 열심히 해본 결과 표를 그려서 규칙을 찾자는 결론에 도달하였다.

처음 해온 생각을 그대로 가져와 무슨 수든 5로 나눠야 최소를 가질 수 있기에 5를 이용한 표를 그렸다.

한글로 하나하나 만든 표이다!.

이 표를 작성하면서 나온 규칙을 정리하자면

5로 나눈 나머지값은 항상 0~4까지의 수이다.

나머지값을 기준으로 

1. 나머지가 0일때 봉지의 수 = n/5의 몫 

2. 나머지가 1일때 봉지의 수 = n/5의 몫+1

3. 나머지가 2일때 봉지의 수 = n/5의 몫+2

4. 나머지가 3일때 봉지의 수 = n/5의 몫+1

5. 나머지가 4일때 봉지의 수 = n/5의 몫+2 

라는 규칙을 찾아냈다 

package test;

import java.util.Scanner;

public class test {

	public static void main(String[] args) {
		Scanner sc =new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();
		
		if(n==4||n==7||n==1||n==2) {
			System.out.println("-1");
		}
		else if(n%5==0) {
			System.out.println(n/5);
		}
		else if(n%5==1||n%5==3) {
			System.out.println(n/5+1);
		}
		else if(n%5==2||n%5==4) {
			System.out.println(n/5+2);
		}
	}
}

수많은 트라이 끝에..! ㅠㅠㅠ  흐뭇하다!