백준 문제풀이 3053번 택시 기하학

2021/11/18 #algorithm #boj #bronze #basic-math

[백준 문제풀이] 3053번 택시 기하학

3053번 택시 기하학 (Bronze 3)

문제

https://www.acmicpc.net/problem/3053

19세기 독일 수학자 헤르만 민코프스키는 비유클리드 기하학 중 택시 기하학을 고안했다.

택시 기하학에서 두 점 T1(x1,y1), T2(x2,y2) 사이의 거리는 다음과 같이 구할 수 있다.

D(T1,T2) = x1-x2 + y1-y2

두 점 사이의 거리를 제외한 나머지 정의는 유클리드 기하학에서의 정의와 같다.

따라서 택시 기하학에서 원의 정의는 유클리드 기하학에서 원의 정의와 같다.

원: 평면 상의 어떤 점에서 거리가 일정한 점들의 집합

반지름 R이 주어졌을 때, 유클리드 기하학에서 원의 넓이와, 택시 기하학에서 원의 넓이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 반지름 R이 주어진다. R은 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다.

풀이

택시 기하학의 개념을 이해하는게 푸는 것보다 오래 걸렸다. 결국 내용을 이해해보면, 택시 기하학에서는 원의 넓이가 2*r^2 였다.

Read more

백준 문제풀이 4153번 직각삼각형

2021/11/18 #algorithm #boj #bronze #basic-math

[백준 문제풀이] 4153번 직각삼각형

4153번 직각삼각형 (Bronze 3)

문제

https://www.acmicpc.net/problem/4153

과거 이집트인들은 각 변들의 길이가 3, 4, 5인 삼각형이 직각 삼각형인것을 알아냈다. 주어진 세변의 길이로 삼각형이 직각인지 아닌지 구분하시오.

입력

입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다.

출력

각 입력에 대해 직각 삼각형이 맞다면 “right”, 아니라면 “wrong”을 출력한다.

풀이

피타고라스의 정리를 이용해서 풀 수 있었다. 나는 최댓값을 구해 빗변으로 삼은 뒤 배열에서 제거해서 했는데, 다른 사람들의 풀이를 보니 정렬을 사용하면 더 효율적으로 할 수 있다는 걸 배웠다.

소스코드 (피타고라스의 정리)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const fs = require("fs");

const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const answerArr = [];
let count = 0;

function isRight(triangle) {
  answerArr.push("wrong");
  const hypo = Math.max(...triangle);
  const index = triangle.indexOf(hypo);
  triangle.splice(index, 1);
  if (
    Math.pow(hypo, 2) ===
    Math.pow(triangle[0], 2) + Math.pow(triangle[1], 2)
  ) {
    answerArr[count] = "right";
  }
}

while (parseInt(input[count][0]) !== 0) {
  const tri = input[count].split(" ").map((num) => parseInt(num));
  isRight(tri);
  count++;
}

console.log(answerArr.join("\n"));
Read more

백준 문제풀이 9020번 골드바흐의 추측

2021/11/17 #algorithm #boj #silver #basic-math

[백준 문제풀이] 9020번 골드바흐의 추측

9020번 골드바흐의 추측 (Silver 1)

문제

https://www.acmicpc.net/problem/9020

1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고 짝수 n이 주어진다.

출력

각 테스트 케이스에 대해서, n보다 크고, 2n보다 작거나 같은 소수의 개수를 출력한다.

풀이

각 테스트 케이스에 대해서 주어진 n의 골드바흐 파티션을 출력한다. 출력하는 소수는 작은 것부터 먼저 출력하며, 공백으로 구분한다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
const fs = require("fs");

const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const T = parseInt(input[0]);
const answerArr = [];

for (let i = 1; i <= T; i++) {
  const number = parseInt(input[i]);
  let a = number / 2;
  let b = number - a;

  while (true) {
    let isPrime = true;
    if (a % 2 === 0 || b % 2 === 0) {
      if (!(a === 2 && b === 2)) {
        isPrime = false;
      }
    } else {
      for (let m = 3; m <= Math.sqrt(a); m += 2) {
        if (a % m === 0) {
          isPrime = false;
          break;
        }
      }
      if (isPrime) {
        for (let n = 3; n <= Math.sqrt(b); n += 2) {
          if (b % n === 0) {
            isPrime = false;
            break;
          }
        }
      }
    }
    if (isPrime) {
      answerArr.push(`${a} ${b}`);
      break;
    } else {
      a -= 1;
      b += 1;
    }
  }
}

console.log(answerArr.join("\n"));

사족 (2022.04.26)

이 당시에는 소수를 구하는 방식으로 풀었는데, 지금 돌아보면 에라토스테네스의 체로 접근하는 것이 더 나은 풀이 같다.

Read more

백준 문제풀이 3009번 네 번째 점

2021/11/17 #algorithm #boj #bronze #basic-math

[백준 문제풀이] 3009번 네 번째 점

3009번 네 번째 점 (Bronze 3)

문제

https://www.acmicpc.net/problem/3009

세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오.

입력

세 점의 좌표가 한 줄에 하나씩 주어진다. 좌표는 1보다 크거나 같고, 1000보다 작거나 같은 정수이다.

출력

직사각형의 네 번째 점의 좌표를 출력한다.

제한
1 ≤ w, h ≤ 1,000
1 ≤ x ≤ w-1
1 ≤ y ≤ h-1
x, y, w, h는 정수

풀이

직사각형을 만들기 위해 입력에 주어지는 x, y 값들이 결국 두 번씩 반복되어야 한다. x, y 각각 배열을 만들어서 풀었다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const fs = require("fs");

const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const a = input[0].split(" ");
const b = input[1].split(" ");
const c = input[2].split(" ");

const line = [a, b, c];

const xArr = [];
const yArr = [];

let x;
let y;

for (let i = 0; i <= 2; i++) {
  xArr.push(parseInt(line[i][0]));
  yArr.push(parseInt(line[i][1]));
}

for (let l = 0; l <= 2; l++) {
  const xDot = parseInt(line[l][0]);
  const yDot = parseInt(line[l][1]);
  if (xArr.indexOf(xDot) === xArr.lastIndexOf(xDot)) {
    x = xDot;
  }
  if (yArr.indexOf(yDot) === yArr.lastIndexOf(yDot)) {
    y = yDot;
  }
}

console.log(`${x} ${y}`);
Read more

백준 문제풀이 1085번 직사각형에서 탈출

2021/11/17 #algorithm #boj #bronze #basic-math

[백준 문제풀이] 1085번 직사각형에서 탈출

1085번 직사각형에서 탈출 (Bronze 3)

문제

https://www.acmicpc.net/problem/1085

한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 x, y, w, h가 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다.

제한
1 ≤ w, h ≤ 1,000
1 ≤ x ≤ w-1
1 ≤ y ≤ h-1
x, y, w, h는 정수

풀이

x, y, w, h, 0, 0 간의 차이 비교를 통해 간단히 풀 수 있었다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const fs = require("fs");

const input = fs.readFileSync("/dev/stdin").toString().trim().split(" ");

const x = parseInt(input[0]);
const y = parseInt(input[1]);
const w = parseInt(input[2]);
const h = parseInt(input[3]);

let min;

if (w - x < x) {
  min = w - x;
} else {
  min = x;
}

if (h - y < y) {
  if (h - y < min) {
    min = h - y;
  }
} else if (min > y) {
  min = y;
}

console.log(min);
Read more