[algorithm] 백준 단계별 문제 풀이 (기본 수학 1 - 1탄)

[algorithm] 백준 단계별 문제 풀이 (기본 수학 1 - 1탄)

 

안녕하세요. 심심한 코딩쟁이입니다.

 

오늘은 기본적인 수학 지식을 사용하는 문제들로 구성해 보았습니다.

 

파이썬3 를 사용해 문제 풀이를 진행하겠습니다.

 

문제마다 링크를 걸어두었으니 문제를 살펴보시고 문제를 푼 다음에 저와

 

풀이를 비교해 보시는 걸 추천드립니다.

차근차근 풀어봅시다.

 

알고리즘

---

백준 BAEKJOON 2292

 

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

 

2292번: 벌집

 

문제 해석

 

벌집 칸에 매겨지는 번호의 규칙을 찾아 문제에서 주어지는 번호의 칸까지

1번에서 최소 몇 칸을 이동해야 하는지 출력하는 문제 첫 위치와 마지막 위치를 포함한 칸의 개수를 출력한다.

 

풀이

 

n = int(input())

total = 1
cnt = 1

while n > total:
    total += cnt*6
    cnt+=1

print(cnt)

 

 

풀이 해석 및 팁

 

1번 칸을 기준으로 한 겹씩 늘어날 때마다 칸의 개수가 6의 배수만큼 커지는 것이 확인되므로

반복문안에서 cnt * 6 을 활용하고 한 겹이 늘어나는 것을 cnt += 1 로 표현합니다.

---

백준 BAEKJOON 1193

 

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

 

1193번: 분수찾기

 

문제 해석

 

문제가 원하는 x번째 분수를 출력하는 문제이다.

표의 첫 번째 칸에서 대각선 방향 지그재그 순서로 분수의 번호가 매겨지는데

번호가 매겨질 때의 규칙을 찾아내는 것이 핵심입니다.

 

풀이

 

n = int(input())
line = 1

while n > line:
    n -= line
    line += 1
if line % 2 == 0:
    print(f"{n}/{line - n + 1}")
else:
    print(f"{line - n + 1}/{n}")

 

풀이 해석 및 팁

 

대각선으로 표를 훑을 때 대각선 줄을 기준으로 살펴보면 짝수번째 줄에서는 분모가 해당하는 짝수로

시작하는 규칙을 찾을 수 있습니다.

---

백준 BAEKJOON 2869

 

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

 

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

 

문제 해석

 

달팽이가 낮에 a만큼 올라가고 밤에는 b만큼 미끄러질 때 v높이의 막대를 오르는데 며칠이 걸리는지 구하는 문제

 

풀이

 

import sys

a, b, v = map(int, sys.stdin.readline().rstrip().split())

print((v-b)//(a-b)+1 if (v-b)%(a-b) != 0 else (v-b)//(a-b))

 

풀이 해석 및 팁

 

풀이에는 print 문 안에 3항 연사자를 이용하였습니다.

참일 때 if (조건) else 거짓일 때

코드를 살펴보면 if와 else 사이에  (v-b)%(a-b) != 0 이 조건으로 자리해 있습니다.

(v-b)은 달팽이가 낮에 이미 정상에 도달해서 미끄러지지 않는 경우를 생각해 주는 방법입니다.

여기에 (a-b)로 나눴을 때 나머지가 0인가 아닌가를 조건으로 두었는데 (a-b)는 하루에

달팽이가 올라갈 수 있는 높이를 의미합니다.

즉, (v-b)%(a-b)가 0이면 달팽이가 정확하게 소수점 없이 며칠 만에 정상에 도달했다는 의미이며

0이 아니면 하루에 올라갈 수 있는 높이 보다는 작은 높이만큼 남아서 하루를 더 올라야 한다는 의미입니다. 

간단한 수를 대입해서 생각해 보시면 이해하기 쉽습니다.

---

여기까지 백준 단계별 문제풀이 기본 수학 1 - 1탄의 풀이 내용이었습니다.

 

문제들의 난이도가 조금 올라간 느낌을 받으셨을지도 모르겠습니다.

 

간단한 문제를 푸는 것보다 이렇게 규칙을 찾기 위해 생각해 보고 생각해 낸

 

풀이법을 코드로 구현해 보는 방법이 가장 좋은 공부법이라고 생각됩니다.

 

궁금하신 점이나 도움이 필요하신 분들은 댓글로 남겨주세요.

 

감사합니다.