[Java] 백준 bruteforcing - 실버모음1

 

 

브론즈 문제는 너무 쉬워서 바로 실버를 푸는 것도 괜찮을 것 같은 브루트포스 문제! 

실버문제들을 풀어보려고 한당

 

1476 날짜제작 실버5

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int resultE = Integer.parseInt(st.nextToken());
    int resultS = Integer.parseInt(st.nextToken());
    int resultM = Integer.parseInt(st.nextToken());

    int E = 1;
    int S = 1;
    int M = 1;

    int cnt = 1;
    while(true) {
      if (E == resultE && S == resultS && M == resultM) {
        System.out.println(cnt);
        return;
      }

      cnt++;

      if (++E == 16) E = 1;
      if (++S == 29) S = 1;
      if (++M == 20) M = 1;
    }

  }
}

수학식으로 한방에 풀려고 시도하면 시간이 많이 드는 문제 ㅎㅎ..ㅠㅠ

그냥 1씩 증가시키면서 풀어도 빠른 시간 내에 답이 나온다! 컴퓨터는 생각보다 계산이 매우 빠르다 

 

 

4673 셀프 넘버 실버5

public class Main {

  public static void main(String[] args) {

    boolean[] notSelfNum = new boolean[10001];
    notSelfNum[1] = true;
    System.out.println(1);

    for (int i =1; i<10001; i++){
      String string = String.valueOf(i);
      int selfNum = i;

      for (int j =0; j<string.length(); j++)
        selfNum += Character.getNumericValue(string.charAt(j));

      if (selfNum <= 10000)
        notSelfNum[selfNum] = true;
    }

    for (int i =1; i<10001; i++) {
      if (!notSelfNum[i])
        System.out.println(i);
    }
  }
}

• d 함수에 규칙같은 건 없음
• self넘버가 맞는지 아닌지는 직접 구해봐야 알 수 있음
• 10000은 계산하기 부담되는 숫자가 아님 + boolean배열 크기로 만들기도 부담스럽지 않음
• 브루트포스!

 

1065 한수 실버4

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int input = Integer.parseInt(br.readLine());

    //한자리면 그대로 반환
    if (input <= 9) {
      System.out.println(input);
      return;
    }

    //한자리 모두 추가 (1~9)
    int result = 9;

    for (int i =1; i<10; i++) {
      //2자리
      for (int add= -i; add<10-i; add++) {
        if (i*10 + i+add <= input)
          result++;
      }

      if (String.valueOf(input).length() == 2)
        continue;

      //3자리
      for (int add = -(i/2); add <= 4 - i/2; add++) {
        if (i*100 + (i+add)*10 + i + 2*add <= input)
         result++;
      }
    }

    System.out.println(result);
  }
}

• 한자리 숫자면 그대로 반환
• 한자리 숫자 이상이라면 1~9를 result에 일단 넣기
• 두자리 숫자면 -i ~ 10-i 까지 더할 수 있기 때문에 for문에 그렇게 추가해줌(이유는 밑에 설명)
  • 입력으로 받은 숫자보다 작으면 result를 1 추가
• 세자리 숫자면 -(i/2) ~ 4-(i/2) 까지 더할 수 있기 때문에 for문에 그렇게 추가해줌
  • result 1 추가~

 

왜 for문에 저렇게 넣었는지 조금 더 설명

[1]
10 => -1이 최소 
19 =>  8이 최대
=> -i  ~  9-i

[9]
90 => -9가 최소
99 =>  0이 최대
=> -i ~ 9-i

• 시간을 줄이려고 한 게 큼
• 두 자리 수의 경우 저 공식이 무조건 성립함. for문에 저렇게 넣어주면 자릿수가 9를 초과하거나 0미만인 걸 체크하지 않아도 됨

 

[1]
111 =>  0이 최소
159 ->  4가 최대
=> -(i/2) ~ 9/2-(i/2)   

[9]
951 => -4가 최소
999 ->  0이 최대
=> -(i/2) ~ 9/2-(i/2)

• 세자리수도 마찬가지임
• 1이랑 9 끝자리만 확인해도 쉽게 공식이 도출된다

 

4375 1 실버3

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

//[baekjoon] java-4375
public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int input;
    StringBuffer sb = new StringBuffer();

    while (true) {
      try {
        input = Integer.parseInt(br.readLine());

        int num = 1;
        int result = 1;
        while(num % input != 0) {
          num = (num*10 + 1)%input;
          result++;
        }

        System.out.println(result);
      } catch (Exception e) {
        return;
      }
    }
  }
}

• 시간초과, 메모리초과로 굉장히 고생한 문제(이럴거면 빨리 구글링할껄..)
  • 모든 경우를 돌려도 안되고, 111... 이렇게 1을 하나 추가시키면서 나누는 것도 시간초과가 난다
• 나머지연산의 규칙을 알아야하는 문제임

 

나머지 연산 규칙

• y = a*x + b
• x를 어떤 정수 k로 나눈 나머지 R 
• y를 어떤 정수 k로 나눈 나머지 R'
• 이 때 R' = a*R + b  임을 증명한다
• y를 k로 나눴을 때 몫은 a*Q이고 나머지는 a*R + b이다.

 

 

교훈: 너무 안풀리면 빠르게 구글링을 해보자

 

1182 부분수열의 합 실버2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//[baekjoon] java-4375
public class Main {

  private static int cnt;
  private static int s;
  private static int[] arr;
  private static int result;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    cnt = Integer.parseInt(st.nextToken());
    s = Integer.parseInt(st.nextToken());
    arr = new int[cnt];

    st = new StringTokenizer(br.readLine());
    for(int i =0; i<cnt; i++)
      arr[i] = Integer.parseInt(st.nextToken());

    dfs(0, 0);

    System.out.println((s == 0)? result-1:result);
  }

  private static void dfs(int depth, int sum) {
    if (depth == cnt) {
      if (sum == s)
        result++;
    } else {
      dfs(depth+1, sum+arr[depth]);
      dfs(depth+1, sum);
    }
  }
}

• (내가 못풀어서 풀이를 찾아본 문제 ㅠㅠ dfs인 걸 캐치했으면 어렵지 않았을듯하다)
  • 참고한 풀이! 감사하다고 댓글도 달았음
  • https://velog.io/@ilil1/%EB%B0%B1%EC%A4%80-1182%EB%B2%88-java
• 각 수열의 원소가 (1)포함되는 경우 (2)포함되지 않는 경우로 트리를 만들어 dfs로 끝점을 계산해야한다
• 주어진 수열에는 규칙이 없기 때문에 백트래킹에서 가지치는 게 불가능하다 (= 모든 경우를 다 생각해야함)
• 풀이
  1. 입력을 받음
  2. depth = 0, sum = 0으로 dfs시작
  3. (1)원소가 포함되는 경우 (2)원소가 포함되지 않는 경우 두 개를 나누어 dfs함수를 재귀호출해줌
  4. 만약 depth가 원소개수와 같아지면 해당 합이 s와 같은지 확인하고, 같으면 result를 하나 증가시켜준다
  5. s가 0인 경우에는 공집합의 경우가 포함되기 때문에 1을 빼줘야한다

그림으로 설명

• 가장 끝 노드만 합을 s와 비교해야함
• 가장 오른쪽은 모든 원소를 선택하지 않은 경우임