[SWEA] 17937, 17642, 17319, 16910, 16800 (D3)

 

17937 큰 수의 최대공약수(D3)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AYmRI_8ajv8DFARi&categoryId=AYmRI_8ajv8DFARi&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1 

SW Expert Academy

 

흔하디 흔한 최대공약수 찾기 문제로 보였다. 최대공약수를 찾기위해서 에라토스테네스의 체를 사용해야한다는 것도 알고, 시간초과가 관건이라는 것도 잘 알았다.

그리고 문제에서 입력될 자연수가 BigInt로 저장해야 한다고 했다! Integer와 같은 자료형보다 사용이 조금 까다로웠던 기억이 난다. 

 

조금 더 시간을 줄일 수 있는 방법을 떠올려봤다.

사이값이라고 하면 1이 더해진 값이 추가될 가능성이 높다 -> 30과 31의 최소공약수 1, 2와 3 최소공약수 1.. 

A	B	최소공
1	2	1
1	1	1
2	3	1
3	4	1
4	5	1
5	6	1
6	7	1
7	8	1
8	9	1

 

아니.. 입력값의 차이가 1이상이 나면 무조건 최소공약수가 자동 1이다. 예외가 없는데..?

약간 꼬아서 생각해보면 같은 값이 나오거나, 1이 나와야하는 것 같았다.

도박을 한 번 해볼까 싶었다

• 같은 값이라면 해당 값을 출력
• 1이라도 차이난다면 1..

가보자!

 

ㅋㅋㅋㅋㅋㅋ 아싸!

 

 

간단한 풀이

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tcCnt = Integer.parseInt(br.readLine());

StringBuffer sb = new StringBuffer();
for (int tc =1; tc<=tcCnt;tc++) {
  StringTokenizer st = new StringTokenizer(br.readLine());
  String tmp = st.nextToken();
  String result;

  if (tmp.equals(st.nextToken()))
    result = tmp;
  else
    result = "1";

  sb.append("#" + tc + " " + result + "\n");
}

System.out.println(sb);

 

 

17642 최대 조작 횟수(D3) - 못풀었음, tc 5개 실패

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AYj_Dz-6qLgDFASl&categoryId=AYj_Dz-6qLgDFASl&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1 

SW Expert Academy

• 최대한 많은 횟수 조작
• 소수를 더해야한다 (1은 소수가 아님)

 

소수라 규칙이 없어서 더 고민이 됐다. 그래서 일단 소수들을 줄줄 적어봄

 

2	3	5	7
11	13	17	19	23
29	31	37	41	43
47	53	59	61	67
71	73	79	83	89

 

a값에 더하나 b값에 빼나 상관없기 때문에 그냥 a에 소수를 더해서 b를 만들어준다고 생각하면 될듯

 

풀이법 초안

1. a와 b사이의 차이 diff를 구함 -> 이제 소수들을 더해서 diff만드는 문제로 변경
2. 2이상 diff이하인 모든 소수 구하기 -> arr
3. 일단 그리디하게 가장 작은 수부터 더해줌 

 

더 성능을 좋게만들기 위해 한가지 생각을 더 해봤다.

• 어차피 차이는 짝수아니면 홀수다
• 짝수면 2만 계속 더해주면 되고, 홀수면 마지막에 3을 더해주는 식으로 하면 되지않나?

 

2와 3만 이용한 풀이법

• 만약 짝수면 2로 나눈 몫이 result
• 홀수면 3을 뺀 걸 2로 나눈 몫 + 1 이 result

 

풀이(통과못함)

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int tcCnt = Integer.parseInt(br.readLine());

StringBuffer sb = new StringBuffer();
for (int tc =1; tc<=tcCnt;tc++) {
  long result = -1L;

  StringTokenizer st = new StringTokenizer(br.readLine());
  long a = Long.parseLong(st.nextToken());
  long b = Long.parseLong(st.nextToken());
  long num = (a>b)? a-b: b-a;

  if (num == 0L) {
    result = 0L;
  } else if (num > 1) {
    if (num % 2 ==0)
      result = num/2;
    else
      result = (num-3)/2 + 1;
  }

  sb.append("#" + tc + " " + result + "\n");
}

System.out.println(sb);

테스트케이스 중 41개는 맞았는데 나머지는 틀렸다. 

 

41개 맞음. 근데 원인을 모르겠다... 

혹시 자료형 문제인가 싶어 BigInt로 바꿔도 봤는데 풀리질 않는다. 

사실 중복이 안되는건가? 그렇다기엔 테스트케이스 41개가 맞았다고 한다.

(구글링 해봐도 답이 나오지 않아서 아시는 분은 댓글 좀 부탁드립니다..ㅠ)

 

이 한문제에 시간을 너무 쏟는 것 같아 안풀고 넘어가려고 한다.

 

17319 문자열문자열(D3)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AYgEiwbKy48DFARP&categoryId=AYgEiwbKy48DFARP&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1 

SW Expert Academy

그냥 반 쪼개서 동일한지 확인하면 될 듯. 멋진 알고리즘은 필요하지 않은 것 같다.

• 홀수면 무조건 불가능
• 짝수면 0부터 num/2-1 까지 배열같은 데 넣고 뒤에꺼 비교하면 될듯

 

int len = Integer.parseInt(br.readLine());
String str = br.readLine();

String result = "Yes";

if (len % 2 != 0) {
    result = "No";
} else {
    char[] arr = new char[len/2];
    for (int i =0; i<len; i++) {
      if (i < len/2) {
        arr[i] = str.charAt(i);
      } else {
        if (str.charAt(i) != arr[i-len/2]) {
          result = "No";
          break;
        }
      }
    }
}

sb.append("#" + tc + " " + result + "\n");

• 이전 문제에 비해 너무 쉬워서 좀 허탈하다

 

 

16910 원 안의 점(D3)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AYcllbDqUVgDFASR&categoryId=AYcllbDqUVgDFASR&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1 

SW Expert Academy

 

• 원점과의 거리가 반지름보다 작거나 같은 애들을 구하면 되겠다.
  • 경계선에 있는 값, 원점 모두 포함한다
• 브루트포스를 쓰면 될 것 같다가도 다른 공식이 있을 것 같아서 찝찝했다. 근데 기억이 안남 ㅋ 
• 모르겠으니 일단 브루트로 풀고 생각을 해보겠다. 

 

시간을 줄일 방법 생각

• 일단 부채꼴 하나만 계산(1사분면), 경계선은 제외
• 4를 곱하고 경계선에 있는 값들을 더해줌

 

풀이방법 초안

1. y가 N일 때 가능한 경우 -> 경계선값 
2. y가 N-1일 때 가능한 경우: (0,0) ~ (x, N-1) 거리가 반지름인 x값을 찾고, 1~x까지 개수를 result에 더함
3. y가 N-2일 때 가능한 경우: (0,0) ~ (x, N-2) 거리가 반지름인 x값을 찾고, 1~x까지 개수를 result에 더함
4. ....
5. 4를 곱하고 경계선 개수를 더해줌 (4*N + 1)

 

풀이

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

public class Solution {

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

    StringBuffer sb = new StringBuffer();
    for (int tc =1; tc<=tcCnt;tc++) {
      int N = Integer.parseInt(br.readLine());
      int result = 0;

      //sqrt(x^2 + i^2) < N    =>    ㅌ < sqrt(N^2 - i^2)
      for (int i =1; i<N; i++) 
        result += (int)Math.sqrt(N*N - i*i);

      result *= 4;
      result += (4*N + 1);

      sb.append("#" + tc + " " + result + "\n");
    }

    System.out.println(sb);
  }
}

찐 풀이 자체는 4줄밖에 안된다! 어렵지 않은 문제

 

 

 

 

16800 구구단 걷기(D3)

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AYaf9W8afyMDFAQ9&categoryId=AYaf9W8afyMDFAQ9&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1 

SW Expert Academy

 

• 이 문제를 완전탐색하기에는 시간낭비다
• i x j배열의 가장 끝까지 가는 움직임 횟수는 (i-1) + (j-1)이다
• i와 j의 합이 가장 작도록 하는 i와 j를 구하면 되겠다!

 

방법생각

1. sqrt로 일단 나눈다
2. 1씩 줄여가면서 i가 될 수 있는지 확인
3. 되면 i와 j값을 더한 값이 result

 

주의할 점

• N은 10의 12승이니까 long으로 받아야한다

 

풀이

long N = Long.parseLong(br.readLine());
long i = (long)Math.sqrt(N);
while (N%i != 0)
	i--;

long j = N/i;

sb.append("#" + tc + " " + (i-1 + j-1) +"\n");

 

 

 

 

다른방법 고민

• 수를 구성하는 소수의 개수를 구하는 방법도 생각해봤다
• ex) 60 = 2^2 * 3 * 5 
• 하지만 i + j의 합이 가장 작은 걸 구하려면 여기서도 하나씩 고르면서 연산이 필요했다
  • 구성하는 소수구하는 시간   +   i+j가 최소인 애 구하는 시간
  • 오히려 더 코드가 복잡해질 것 같기도 했다
• 1조의 루트를 구하면 10^6 = 1000000 백만이니까 2초를 안넘을 것 같아서 원래방법 사용함

 

 

 

 

 

백준을 열심히 풀었더니 D3도 풀만한 것 같기도 하다!

그래도 못 푼 문제나 구글링해본 문제가 있어서 열심히해야할 것 같다.