[백준] 기본 수학1 문풀

백설기·2022년 2월 21일
백준백준문풀
0

백준 문풀

목록 보기
4/7

2775번 부녀회장이 될테야

  • 내가 풀이한 코드 (틀림)
package 기본수학1;
import java.util.*;

public class 부녀회장이될테야 {
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int T=sc.nextInt();
		for(int i=0;i<T;i++) {
			int k=sc.nextInt();
			int n=sc.nextInt();
			int[][] people=new int[k+1][n+1];
			for(int j=0;j<=k;j++) {
				for(int m=1;m<=n;m++) {
					if(j==0) {
					people[j][m]=m;
					}
					for(int h=1;h<=m;h++) {
						if(j==1) {
							people[j][m]+=people[0][h];
							}
						else if(j>=2){
							if(h==1) {
								people[j][h]+=people[j-1][h];
							}
							else if(h>=2) {
							people[j][h]+=people[j][h-1]+people[j-1][h];
							}
					}
			}
	}

			
}
			System.out.println(people[k][n]);		
}
}
}

하다가 빡쳐서 구글링 ..^^
2차원 배열 쓰면 풀 수 있을 거 같았는데 for문 변수들 헷갈려서 구글링 선배님들의 풀이를 보고 다시 배웠다

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		
		// 아파트 생성 
		int[][] APT = new int[15][15];
 
		for(int i = 0; i < 15; i++) {
			APT[i][1] = 1;	// i층 1호
			APT[0][i] = i;	// 0층 i호
		}
 
 
		for(int i = 1; i < 15; i ++) {	// 1층부터 14층까지
 
			for(int j = 2; j < 15; j++) {	// 2호부터 14호까지
				APT[i][j] = APT[i][j - 1] + APT[i - 1][j];
			}
		}
		
		// 테스트 부분 		
		int T = in.nextInt();
		
		for(int i = 0; i < T; i++) {
			int k = in.nextInt();
			int n = in.nextInt();
			System.out.println(APT[k][n]);
		}
	}
 
}
  • 놓친 부분: 규칙을 찾고 어떻게 더하면 될지 고심한 부분은 같으나 간단하게 i와 j의 항들을 더하면 될 것을 굳이 어렵게 세세하게 나누어 스스로 헷갈리게 만들었다. 굿노트로 규칙성을 찾았지만, 다음부턴 표를 이용하여 어느 부분이 다르고 2차원 배열에서 각 항마다 어느 차이점이 있는지 파악해 더해나가는 것이 좋을 것 같다..!

1193번 분수찾기

import java.util.*;
public class 분수찾기 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int a =sc.nextInt();
		int cnt=0;
		int n=0;
		while(true) {
			n++;
			cnt+=n;
			if(cnt>=a) {
				if(n%2==0) {
					System.out.println(a-cnt+n+"/"+(cnt-a+1));
				}
				else {
					System.out.println((cnt-a+1)+"/"+(a-cnt+n));
				}
				break;
			}
		}
	}

}

홈페이지에 있는 거처럼 분수들을 표에 나열해보면 규칙을 찾아볼 수 있다.
표를 45도 정도 돌려서 보면 행마다 규칙성을 확인해볼 수 있는데, 바로한 행에 있는 분수들의 분자 분모 합이 같은 것이다!
행의 변수 n, 분수 개수 cnt, 입력한 숫자 번호 a라 두고 while문을 설정하여 n의 수를 올릴 때마다 cnt를 더한 후, cnt와 a의 크기를 비교한다. 이때 cnt이 a보다 크거나 같다면 해당 n행에 a가 있는 것이 파악되므로 그 때의 if문을 걸어 분자 분모를 구할 수 있다. 짝수 행일 때는 a-cnt+n/cnt-a+1, 홀수 행일 땐 그 반대이다. 구글링해서 나온 다른 분들의 답도 추가했다!
짝수행이라면 분모가 감소하는 방향이니 cnt-a를 먼저 계산해주고 1을 더해준다. 분자는 증가하는 방향이니 반대로 a-cnt를 계산해준 뒤 n을 더하여 양수값을 만들어준다. 갠적으로 난 이 방법이 더 계산하기 편했던 거 같다!

import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
		int X = in.nextInt();
 
		int cross_count = 1, prev_count_sum = 0;
 
		while (true) {
        
			// 직전 대각선 누적합 + 해당 대각선 개수 이용한 범위 판별
			if (X <= prev_count_sum + cross_count) {	
				
				if (cross_count % 2 == 1) {	// 대각선의 개수가 홀수라면 
					// 분모가 큰 수부터 시작
					// 분모는 대각선 개수 - (X 번째 - 직전 대각선까지의 누적합 - 1) 
					// 분자는 X 번째 - 직전 대각선까지의 누적합 
					System.out.print((cross_count - (X - prev_count_sum - 1)) + "/" + (X - prev_count_sum));
					break;
				} 
				
				else {	// 대각선의 개수가 짝수라면 
					// 홀수일 때의 출력을 반대로 
					System.out.print((X - prev_count_sum) + "/" + (cross_count - (X - prev_count_sum - 1)));
					break;
				}
 
			} else {
				prev_count_sum += cross_count;
				cross_count++;
			}
		}
	}
}

입력받을 X 값
해당 범위의 대각선 칸 개수 ( cross_count )
해당 대각선 직전 대각선 까지의 칸의 누적 합 ( prev_count_sum )

  • 놓친 부분: 첨에는 분자 분모를 (,)식으로 두어 한쪽 수가 늘 때마다 규칙을 부여해 if문으로 구별하려 했는데 그렇게 하려니 넘 복잡했다. 그래서 구글링의 힘을 받아 (..^^) 간단한 규칙성을 발견할 수 있었다. 바로 행별로 분자 분모 합이 같은 것.. 그리고 if문에서 짝수행, 홀수행별로 분자 분모가 다른데 이때 분자 분모를 구하는 식 a-cnt+n+"/"+(cnt-a+1)을 놓쳤다.

2869번 달팽이는 올라가고 싶다

import java.util.*;
public class 달팽이는올라가고싶다 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc= new Scanner(System.in);
		int A=sc.nextInt();
		int B=sc.nextInt();
		int V=sc.nextInt();
		int h=A;
		int day=1;
		while(h<V) {
			h-=B;
			day++;
			h+=A;
		}
		System.out.println(day);
	}

}

값은 맞다. 그러나 예시 3번과 같은 경우 적용했을 때 넘 오래걸린다..
반복문을 쓸 경우 무조건 시간초과되기에 더 적은 시간 소요될 수 있는 알고리즘을 생각해보았다. 우선 A B V간의 관계성을 파악해보았다.

ABVday
2154
5162
100991000000000999999901

그냥 편하게 전체 길이에서 A-B만큼을 나눠주면 되는데 이와 같은 경우 정점에 도달했을 때도 미끄러짐을 전제하에 계산하는 것과 같다. 그러기에 V-B, 즉 정상 도달 전 마지막으로 미끄러지는 길이에서 A-B을 나눠주면 day값 계산 완료. 근데 정확히 나눠지지 않는 경우는 if문으로 예외를 세워 기존 day값에 +1을 해준다..!

놓친부분: 정확히 나눠지지 않는 부분을 어떻게 해결할까에서 고민되었다. 새로 식을 세울까 했는데 그냥 단순히 day++라는 식을 세우면 끝이었음

import java.util.*;
public class 달팽이는올라가고싶다 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc= new Scanner(System.in);
		int A=sc.nextInt();
		int B=sc.nextInt();
		int V=sc.nextInt();
		int day=(V-B)/(A-B);
		if((V-B)%(A-B)!=0) {
			day++;
			}
		System.out.println(day);
}
}

그런데도 java11에서는 시간초과 떠서 결국 구글링의 힘으로 Buffer 이용한 코드로 작성했다..

2292번 벌집

import java.util.Scanner;
class Main {
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int num=sc.nextInt();
    int range1=1;
    int range2=1;
    int cnt=1;
    while(true){
      if(range1<=num && num<=range2){
        System.out.print(cnt);
        break;
      }
      else{
        range1=range2+1;
        range2+=6*cnt;
        cnt++;
        }
    }
  }
}
  • 체크 포인트: 1~1, 2~7 (6개), 8~19 (12개), 20~ 37 (18개), 38~61 (24개) 등... 구간을 잡아보면 규칙적으로 6의 배수만큼 범위가 커진다. 이 부분을 잡아 if문에 num 범위를 잡고, 해당 범위가 아닐 경우 range1은 range2 바로 다음 숫자로 잡고, range2는 범위가 6의 배수만큼 커져야하기에 6과 cnt를 곱한 수를 range2와 더했다. 그리고 cnt를 점점 더해가며 범위를 늘려주었다!

10250번 ACM 호텔

import java.util.Scanner;
class Main {
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
      int T=sc.nextInt();
    for(int i=0;i<T;i++){
      int h=sc.nextInt();
      int w=sc.nextInt();
      int n=sc.nextInt();
      int y=0;
      int x=0;
      
      if(n%h==0){
        y=h;
      }
      else{
        y=n%h;
      }
      if(n%h>0){
        x=n/h+1;
        }
      else if(n%h==0){
        x=n/h;
      }
      if(x<10){
        System.out.println(y+"0"+x);
      }
      else {
        System.out.println(y+""+x);
      }
    }
  }
}
  • 초점 맞춘 부분: 나머지가 0으로 떨어지는 부분에 집중했다. if문으로 각각 y, x에 나머지가 0으로 떨어지는지 여부를 나눴는데, 이를 안나눈다면 30 50 1500과 같은 케이스에 오류가 생긴다. 호(x)같은 경우 나머지가 0보다 큰지, 0인지로 나누어 호수(x)를 정하였다!

1712번 손익분기점

import java.util.Scanner;
class Main {
 public static void main(String[] args) {
 Scanner sc= new Scanner(System.in);
   long A=sc.nextInt();
   long B=sc.nextInt();
   long C=sc.nextInt();
   long cnt=1;

   while(true){
     if(A+B*cnt<C*cnt){
       System.out.println(cnt);
       break;
       }
     else if(B>C){
       cnt=-1;
       System.out.println(cnt);
     break;
       }
     else{
       cnt++;
     }
     
   }
 }
}
  • 초점 맞춘 부분:
    while문으로 돌리니 시간 초과 뜬다! A B C 억이 넘어가는 숫자면,,
    그래서 단순하게 cnt 값을 정해주고 B가 C랑 크거나 같을 때만 조건 걸어줘서 시간 단축해줬다.
    import java.util.Scanner;
    class Main {
      public static void main(String[] args) {
      Scanner sc= new Scanner(System.in);
        int A=sc.nextInt();
        int B=sc.nextInt();
        int C=sc.nextInt();
        long cnt=1;
        if(B>=C){
            cnt=-1;
            System.out.println(cnt);
            }
        else{
        cnt=A/(C-B)+1;   
        System.out.println(cnt);
          }

      }
    }

10757번 큰 수 A+B

  				
       import java.util.Scanner;
       import java.math.BigInteger;

	   class Main{
       public static void main(String[] args){
          Scanner sc = new Scanner(System.in);

          BigInteger a = sc.nextBigInteger();
          BigInteger b = sc.nextBigInteger();

          System.out.println(a+b); //or 	System.out.println(a.add(b));
          }
         }
  • 간단하게 BigInteger class를 사용하여 더할 수 있다!
    기존의 int, long으로는 범위가 초과되므로...
    그래서 String을 charAt으로 하나씩 받아 배열을 만들어봤다.
	<오류코드>
    import java.util.Scanner;
    class Main {
      public static void main(String[] args) {
      Scanner sc= new Scanner(System.in);
        String A=sc.next();
        String B=sc.next();
        int[] C=new int[A.length()];
      for(int i=A.length()+1;i>=0;i--){
        C[i]=(int)A.charAt(i)+(int)B.charAt(i);      
      if(C[i]>=10){
        C[i]-=10;
        C[i-1]+=1;
        }
      System.out.print(C[i]);
      }      
      }
    }
  • 배열로 만들어봤는데 범위 오류가 계속 떠서 결국 구글링... stranger's lab님의 코드!
	String str_A = input();
	String str_B = input();
 
	int max_length = max(str_A.length(), str_B.length()); 
	int[] A = new int[max_length + 1];	// 마지막 자리수 올림이 있을 수 있으므로 +1
	int[] B = new int[max_length + 1];	// 마지막 자리수 올림이 있을 수 있으므로 +1
 
	// A 초기화
	for(int i = A.length - 1, int idx = 0; i >= 0; i--, idx++) {
	A[idx] = str_A.charAt(i) - '0';	// 맨 뒤 문자부터 역순으로 하나씩 저장
	}
 
	// B 초기화
	for(int i = B.length - 1, int idx = 0; i >= 0; i--, idx++) {
	B[idx] = str_B.charAt(i) - '0';	// 맨 뒤 문자부터 역순으로 하나씩 저장
	}
 
    // 덧셈
    for(int i = 0; i < max_length; i++) {
        int value = A[i] + B[i];
        A[i] = value % 10;	// 더한 값의 10으로 나눈 나머지가 자리값이 됨
        A[i + 1] = A[i + 1] + (value / 10);	// 더한 값의 10으로 나눈 몫이 올림값이 됨
    }

    // A배열 역순 출력
    // 가장 높은 자리수가 0일 수도 있기 때문에 0이 아닐 경우에만 출력
    if(A[max_length] != 0) {
        print(A[max_length]);
    }
    for(int i = max_length - 1; i >= 0; i--) {
        print(A[i]);
    }

  • 체크 포인트:

    1. int max_length = max(str_A.length(), str_B.length());
      A랑 B 길이 중 예시와 다르게 A가 더 길거나 B가 더 길 땐 어떡하지 했는데
      max함수를 이용하여 max_length를 정할 수 있었다.

    2. 초기화 부분에서 역순으로 하나씩 저장할 때 charAt(i)값에 '0'을 뺀 것

    3. 더한 값의 초과 몫을 더할 때 10을 나눈 것.. 단순히 1만 더했었다.

    4. for문에서 범위 설정 중요!!!!!

      이런 알고리즘 익숙할 때까지 더 공부하고 생각하는 능력을 길러야겠다..!

  • charAt(i)만 했을 땐 문자인데, '0'을 빼주면 정수형이다!**

2839번 설탕배달

      import java.util.Scanner;
      class Main {
        public static void main(String[] args) {
          Scanner sc= new Scanner(System.in);
          int N = sc.nextInt();
          int cnt=0;
          int five=0;
          int three=0;
          int ans=0;

          if(N%5/3>0&&N>=5){
            cnt=N%5+N%5/3;
            }
          else if((N%3+3)%5==0&&N>=3){
            cnt=N/3;
          }
          else{
            cnt=-1;
            }

          if(N%5==0){
            five=N/5;
            if(cnt<five&&cnt!=-1){
              ans=cnt;
              }
            else
            {ans=five;}
              if(N%3==0){
                ans=five;
              }
            }
          else if(N%3==0){
            three=N/3;
            if(cnt<three&&cnt!=-1){
              ans=cnt;
            }
            else
            {ans=three;}
            if(N%5==0){
              ans=five;
            }
          }
          else
          {
            ans=cnt;
          }

          System.out.println(ans);
        }
      }
  • 이것저것 추가하다보니 틀렸다........구글링해서 얻은 해답은
    3kg를 거스름돈으로 생각하여 3kg를 덜어낼때마다 5kg로 나눠지는 구간이 있으면
    그 부분들을 5kg 주머니들로 들고 가는 것이다!
    import java.util.Scanner;
    class Main {
      public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int N = sc.nextInt();
        int cnt=0;
        while(true){
         if(N%5==0){
           System.out.print(N/5+cnt);
           break;
         }
         else if(N<0){
           cnt=-1;
           System.out.print(cnt);
           break;
         }
          N=N-3;
          cnt++;
       }
      }
    }
profile
백설기
뭐든지 할 수 있따 🐶
이전 포스트

[백준] 문자열 문제 정리

다음 포스트

[백준] 기본 수학2 문풀

0개의 댓글