백준 문제풀이 1193번 분수찾기

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

[백준 문제풀이] 1193번 분수찾기

1193번 분수찾기 (Bronze 1)

문제

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

무한히 큰 배열에 다음과 같이 분수들이 적혀있다.

1/1 1/2 1/3 1/4 1/5 …
2/1 2/2 2/3 2/4 … …
3/1 3/2 3/3 … … …
4/1 4/2 … … … …
5/1 … … … … …
… … … … … …
이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자.

X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오.

첫 번째 풀이

수학 능력이 머리에 없는건지 도저히 모르겠어서 구글링을 해보았다.

수학적인 사고는 자연어로 이루어진 문제를 분석, 해결 가능한 수준으로 나누고 패턴을 찾아내는 과정이라는 말을 읽고 참 인상 깊게 새겼다. 결국 수학은 복잡한 문제를 단순화하고 패턴을 찾아내서 일반화하는 것이라는 걸 읽고 수학에 대한 새로운 생각을 할 수 있었다.

결국 주기성을 찾아내는 것이라고.

패턴화 하려고 노력했고, 답을 참고하지 않고 풀어낼 수 있었다. 

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
const fs = require("fs");

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

const num = parseInt(input);
let range = 1;
let line = 1;
let answer = 0;
let fraction = 0;

if (num === 1) {
  answer = `1/1`;
} else {
  while (range < num) {
    line++;
    range += line;
  }

  if (line % 2 === 1) {
    fraction = range - num + 1;
  } else {
    fraction = line - (range - num);
  }

  answer = `${fraction}/${line - fraction + 1}`;
}

console.log(answer);
Read more

백준 문제풀이 1712번 손익분기점

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

[백준 문제풀이] 1712번 손익분기점

1712번 손익분기점 (Bronze 4)

문제

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

월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다.

예를 들어 A=1,000, B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만원이 들며, 열 대 생산하는 데는 총 1,700만원이 든다.

노트북 가격이 C만원으로 책정되었다고 한다. 일반적으로 생산 대수를 늘려 가다 보면 어느 순간 총 수입(판매비용)이 총 비용(=고정비용+가변비용)보다 많아지게 된다. 최초로 총 수입이 총 비용보다 많아져 이익이 발생하는 지점을 손익분기점(BREAK-EVEN POINT)이라고 한다.

A, B, C가 주어졌을 때, 손익분기점을 구하는 프로그램을 작성하시오.

첫 번째 풀이

A : 고정 비용, B : 생산당 가변 비용, C : 매출

손익분기점을 구하라. 

1
2
3
4
5
6
7
8
9
10
11
const answer = 0;
let 매출 = -A;

if (B > C) {
	console.log(-1);
} else {
	while (매출 > 0) {
		매출 += (C – B);
		answer++
	};
};

이와 같이 접근했다. => 시간초과

두 번째 풀이

이 문제가 ‘수학 능력’ 카테고리에 있었다는 것을 간과했었다.

반복문을 써서 풀면 당연히 늦어질 수 밖에 없고, 개당 수익으로 고정 손해 나눠준 뒤 반올림 해준 뒤 +1 해주면 되는 일이었다.

풀이 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const fs = require("fs");

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

const a = parseInt(input[0]);
const b = parseInt(input[1]);
const c = parseInt(input[2]);

if (b >= c) {
  answer = -1;
} else {
  answer = Math.floor(a / (c - b)) + 1;
}

console.log(answer);
Read more

백준 문제풀이 2292번 벌집

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

[백준 문제풀이] 2292번 벌집

2292번 벌집 (Bronze 2)

느낀 점

Keep It Super Simple

문제

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

위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.

풀이

수열로 풀이 하려고 했는데, 너무 수학적으로 접근했었다는 것을 깨달았다. 그냥 간단하게 한 줄이 늘어날때마다 한 칸이 늘어나게 된다.

1까지는 1번, 7까지는 2번, 19까지는 3번, 37까지는 4번 이와 같이 이동하게 된다. 이걸 수열로 1, 7, 19와 같은 수를 수열로 생각해서 문제에 접근하였다. 입력된 숫자가 포함되는 범위까지의 수를 찾을 때까지 거리를 하나 씩 추가해주었다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
const fs = require("fs");

const number = parseInt(fs.readFileSync("/dev/stdin").toString());

let distance = 1;
let range = 1;

while (number > range) {
  range += distance * 6;
  distance++;
}

console.log(distance);
Read more

2021.11.08 백준 문제풀이

2021/11/08 #algorithm #boj #silver

2021.11.08. 백준 문제풀이

1316번 그룹 단어 체커 (Silver 5)

문제

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

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다.

단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오.

풀이

먼저 set을 이용해서, 중복되는 문자가 없을 때의 경우를 제외해주고 반복문을 통해 확인하기로 정했다.

소스코드

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
const fs = require("fs");

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

const n = parseInt(input[0]);
let answer = 0;

for (let i = 1; i <= n; i++) {
  const letters = input[i].split("");
  const newLetter = [];
  const set = new Set(letters);
  if (letters.length === set.size) {
    answer += 1;
  } else {
    let isGroupWord = true;
    for (let j = 0; j < letters.length; j++) {
      if (newLetter.indexOf(letters[j]) === -1) {
        newLetter.push(letters[j]);
      } else {
        if (newLetter.indexOf(letters[j]) !== newLetter.length - 1) {
          isGroupWord = false;
          break;
        }
      }
    }
    if (isGroupWord) {
      answer += 1;
    }
  }
}

console.log(answer);

반복문에서는 isGroudWord라는 Boolean 값을 통해서, GroupWord의 상태가 유지되는지 확인하였고, 다른 배열에 문자들을 추가하여서 그 배열의 중복 값이 마지막에 위치해있는지를 통해서 연속적으로 문자가 배치되어있는지 확인했다.

Read more

2021.11.07 백준 문제풀이

2021/11/07 #algorithm #boj #silver

2021.11.07. 백준 문제풀이

2941번 크로아티아 알파벳 (Silver 5)

느낀 점

처음에는 알파벳 문자열 순서에 맞춘 조건문을 사용하려다가 너무 섹시하지 않아서 다른 방법을 고안했다. 정규표현식과 replace로 문자열 대치를 하면 쉽게 풀 수 있을 것 같아서 찾아봤는데 비슷하게 푼 사례가 있어서 참고해서 간단하게 풀 수 있었다.

에러

trim()을 사용안해서 오류가 생겼었다.

문제

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

소스코드

1
2
3
4
5
6
7
8
const fs = require("fs");

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

const regex = /c\=|c\-|dz\=|d\-|lj|nj|s\=|z\=/g;
const output = input.replace(regex, "Q");

console.log(output.length);
Read more