[복습] 단계별-(8) 수학

Leejaegun·2025년 10월 28일

코딩테스트 시리즈

목록 보기

48/49

8단계별에 있는 수학을 풀어봅시다: https://www.acmicpc.net/step

1.벌집

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

N = int(input())

nums_pile = 1
cnt = 1
while N > nums_pile:
    nums_pile += 6 * cnt
    cnt += 1

print(cnt)

배운점

🐝 1. 문제 요약

중앙의 1번 방에서 시작해 육각형 형태로 방이 확장되는 구조이다.
1 → 2~7 → 8~19 → 20~37 … 이런 식으로 확장되며,
각 층(layer)은 6의 배수만큼 방이 증가한다.

🧠 2. 문제의 핵심 논리

각 층의 범위를 보면 다음과 같다.

층	마지막 번호	증가량
1층	1	+0
2층	7	+6
3층	19	+12
4층	37	+18
5층	61	+24

→ 즉, 증가량은 6 × (층 - 1) 의 규칙을 따른다.

결국 “몇 번째 층에 N이 포함되는가?” 를 찾는 문제로 바뀐다.

⚙️ 3. 잘못된 접근 (메모리 초과형)

처음에는 단순히 값을 누적해서 리스트를 만들었다.

def custom(n: int) -> List[int]:
    a = [1]
    diff = 1
    for k in range(2, n + 1):
        a.append(a[-1] + diff)
        diff = 6 * (k - 1)
    return a

하지만 이렇게 하면 불필요한 리스트를 만들어 메모리를 낭비하게 된다.
특히 n이 수십만일 때는 리스트 생성으로 인해 메모리 초과가 발생한다.

🔍 4. 개선된 접근 (계층 누적 방식)

리스트 대신 현재 누적합(nums_pile) 과 층(cnt) 만 추적하면 된다.

N = int(input())

nums_pile = 1  # 현재 층의 마지막 숫자
cnt = 1        # 층 번호

while N > nums_pile:
    nums_pile += 6 * cnt
    cnt += 1

print(cnt)

설명:

nums_pile은 각 층의 마지막 방 번호를 의미.
cnt는 현재 층의 번호.
입력값 N이 현재 층의 마지막 번호보다 크면 다음 층으로 넘어간다.

🧩 5. 시행착오 기록

처음에는 diff를 직접 계산하면서 계층을 누적하려고 했다.

def find_layer(n: int) -> int:
    a = 1
    diff = 1
    k = 1
    while a < n:
        a += diff
        k += 1
        diff = 6 * (k - 1)
    return k

하지만 이 방식은 매 단계에서 diff가 바뀌는 타이밍이 어긋나 정확히 일치하지 않는 문제가 있었다.
결국 위의 간단한 반복문(nums_pile += 6 * cnt) 형태로 정리하면 깔끔하게 해결된다.

🎯 6. 배운 점

불필요한 리스트나 배열을 만들지 말고, 필요한 변수만 유지하자.
“패턴”이 보이면 메모리보다는 수학적 규칙으로 접근하라.
간단한 수학적 수열 문제라도, 증가량(diff)의 규칙을 찾는 것이 핵심이다.

✏️ 7. 마무리 한줄 요약

벌집 문제는 단순 누적이 아닌, 6의 배수로 확장되는 계층 구조를 수학적으로 파악하는 문제였다.
수열의 규칙만 정확히 잡으면 단 세 줄로 풀린다.

2. 분수찾기

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

X = int(input())

line = 1
# 전체 그룹 인덱스를 line이라고 해서 함. 
while X > line *(line+1)//2:
    line += 1

start = line *(line-1) //2 + 1 
idx = X - start

if line % 2 ==0:
    num = 1 + idx
    den = line - idx
else:
    num = line - idx
    den = 1 + idx
    
print(f"{num}/{den}")

이번꺼는 진짜진짜 말도 안되는 문제였다. ~~이게 실버라고?~~

🧠 1. 문제 이해

1번부터 시작해서 대각선으로 분수들이 배치되어 있다.
즉, 다음과 같이 나선형으로 번호가 붙는다.

1/1  
1/2, 2/1  
3/1, 2/2, 1/3  
1/4, 2/3, 3/2, 4/1  
...

즉,
1번째 줄엔 1개,
2번째 줄엔 2개,
3번째 줄엔 3개,
… 이런 식으로 줄(line) 별로 항의 개수가 늘어난다.

⚙️ 2. 규칙 분석

각 줄(line)의 마지막 번호는 다음과 같다.
```
1, 3, 6, 10, 15, ...
```
즉, line × (line + 1) / 2 형태의 삼각수(Triangular Number).
입력 X가 주어졌을 때,
- X가 몇 번째 줄(line)에 속하는지 찾는다.
- 그 줄(line) 안에서 몇 번째 위치(index)에 있는지 구한다.

🧩 3. 단계별 접근

(1) 몇 번째 줄(line)에 속하는지 찾기

line = 1
while X > line * (line + 1) // 2:
    line += 1

line * (line + 1) // 2는 각 줄의 마지막 번호.
X가 그 값을 초과하면 다음 줄로 넘어감.

예:
X=14 →
1, 3, 6, 10, 15 →
10 < 14 ≤ 15 → line = 5

(2) 해당 줄의 시작 index 계산

start = line * (line - 1) // 2 + 1
idx = X - start

start는 해당 줄의 첫 번째 번호.
idx는 그 줄 안에서의 위치(0부터 시작).

예:
line=5 → start=11 →
X=14 → idx=3 (즉, 5번째 줄의 네 번째 원소)

(3) 짝수/홀수 줄 규칙 구분

분모(denominator)와 분자(numerator)의 변화 방향이 서로 다르다.

line	순서 방향	예시
홀수	↙️ 위에서 아래로 (분자가 먼저 줄어듦)	3/1 → 2/2 → 1/3
짝수	↗️ 아래에서 위로 (분모가 먼저 줄어듦)	1/4 → 2/3 → 3/2 → 4/1

이를 코드로 표현하면 다음과 같다.

if line % 2 == 0:  # 짝수 줄
    num = 1 + idx
    den = line - idx
else:               # 홀수 줄
    num = line - idx
    den = 1 + idx

🧩 5. 핵심 요약

줄(line)별 최대 인덱스 = line × (line + 1) // 2
시작 인덱스 = line × (line - 1) // 2 + 1
짝수 줄은 분자 증가, 홀수 줄은 분모 증가

💡 6. 배운 점

패턴을 표로 그려서 분석하는 것이 수학 구현 문제의 핵심.
단순 반복문보다 “수열 공식”으로 구조를 이해하면 코드가 단 한 줄로 정리된다.
“분자(numerator)”와 “분모(denominator)”의 변화 방향이 문제 해결의 핵심이었다.

✏️ 한줄 요약

분수찾기 문제는 ‘삼각수로 그룹을 나누고, 홀짝에 따라 분자·분모의 방향을 바꾸는 규칙 찾기 문제’였다.
단순한 반복이 아니라, 수열의 성질을 관찰하는 훈련이 된다.

3. 달팽이는 올라가고 싶다.

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

A,B,target = map(int,input().split())
import math
day = math.ceil((target - A)/(A-B))+1 # 516 -> 6-5 //4 =>1/4= 1+1
print(day)

배운점
다듬은 블로그 포스팅용 버전은 다음과 같습니다.
불필요한 구문을 정리하고, 문맥을 자연스럽게 구성했어요.

🐌 달팽이는 올라가고 싶다 (BOJ 2869)

📎 문제 링크: https://www.acmicpc.net/problem/2869

A, B, target = map(int, input().split())
import math

day = math.ceil((target - A) / (A - B)) + 1
print(day)

🔍 문제 접근

처음에는 단순하게 시뮬레이션 방식으로 접근했다.

cnt = 0
curr = 0
while curr <= target:
    curr += A
    cnt += 1
    if curr >= target:
        break
    else:
        curr -= B

이 방식은 직관적이지만, target이 매우 클 경우 (10^9 수준)
반복문이 수억 번 돌기 때문에 시간초과(또는 메모리초과) 가 발생한다.

따라서 반복 없이 수식으로 계산해야 한다.

🧠 수식으로 풀이하기

달팽이는 하루에 A만큼 올라가고, 밤에 B만큼 내려간다.
단, 마지막 날에는 내려가지 않는다.

이를 식으로 쓰면 다음과 같다.

(A - B) \times (day - 1) + A \ge target

이때 day를 구하면:

day = \frac{target - A}{A - B} + 1

소수점이 생길 수 있으므로 올림(ceil) 처리해야 한다.

→ 최종 식:

day = math.ceil((target - A) / (A - B)) + 1

💡 배운 점

단순 시뮬레이션으로 접근하면 시간복잡도는 O(target / (A - B))가 되어 매우 비효율적이다.
수식으로 바꾸면 O(1) 계산으로 즉시 답을 구할 수 있다.
math.ceil()은 소수점 이하가 생기면 무조건 올림하기 때문에, 남는 거리 처리에 적합하다.

🧮 코딩테스트에서 자주 쓰이는 `math` 함수 정리

함수	설명	예시	결과
`math.ceil(x)`	올림	`math.ceil(3.2)`	`4`
`math.floor(x)`	내림	`math.floor(3.9)`	`3`
`round(x)`	반올림	`round(3.5)`	`4`
`math.sqrt(x)`	제곱근	`math.sqrt(9)`	`3.0`
`math.pow(a, b)`	거듭제곱 (aⁿ)	`math.pow(2, 3)`	`8.0`
`math.gcd(a, b)`	최대공약수	`math.gcd(12, 8)`	`4`
`math.lcm(a, b)`	최소공배수 (Python 3.9+)	`math.lcm(3, 5)`	`15`
`math.pi`	원주율 π	`math.pi * r**2`	원의 넓이 계산
`math.log(x, base)`	로그 (밑 지정 가능)	`math.log(8, 2)`	`3.0`

✍️ 정리

단순 시뮬레이션 → 시간초과
수식 변환 → O(1) 풀이
ceil 필수 이유: 남은 거리가 조금이라도 있으면 하루 추가

Leejaegun

Lee_AA

이전 포스트

[복습] Python 배우기 100~150

다음 포스트

[복습] 단계별-(8) 수학

코딩테스트 시리즈

1.벌집

배운점

🐝 1. 문제 요약

🧠 2. 문제의 핵심 논리

⚙️ 3. 잘못된 접근 (메모리 초과형)

🔍 4. 개선된 접근 (계층 누적 방식)

🧩 5. 시행착오 기록

🎯 6. 배운 점

✏️ 7. 마무리 한줄 요약

2. 분수찾기

🧠 1. 문제 이해

⚙️ 2. 규칙 분석

🧩 3. 단계별 접근

(1) 몇 번째 줄(line)에 속하는지 찾기

(2) 해당 줄의 시작 index 계산

(3) 짝수/홀수 줄 규칙 구분

🧩 5. 핵심 요약

💡 6. 배운 점

✏️ 한줄 요약

3. 달팽이는 올라가고 싶다.

🐌 달팽이는 올라가고 싶다 (BOJ 2869)

🔍 문제 접근

🧠 수식으로 풀이하기

💡 배운 점

🧮 코딩테스트에서 자주 쓰이는 `math` 함수 정리

✍️ 정리

[복습] Python 배우기 100~150

[복습] 알고리즘 기초 1/2 201-자료구조1(연습+참고)

0개의 댓글

[복습] 단계별-(8) 수학

코딩테스트 시리즈

1.벌집

배운점

🐝 1. 문제 요약

🧠 2. 문제의 핵심 논리

⚙️ 3. 잘못된 접근 (메모리 초과형)

🔍 4. 개선된 접근 (계층 누적 방식)

🧩 5. 시행착오 기록

🎯 6. 배운 점

✏️ 7. 마무리 한줄 요약

2. 분수찾기

🧠 1. 문제 이해

⚙️ 2. 규칙 분석

🧩 3. 단계별 접근

(1) 몇 번째 줄(line)에 속하는지 찾기

(2) 해당 줄의 시작 index 계산

(3) 짝수/홀수 줄 규칙 구분

🧩 5. 핵심 요약

💡 6. 배운 점

✏️ 한줄 요약

3. 달팽이는 올라가고 싶다.

🐌 달팽이는 올라가고 싶다 (BOJ 2869)

🔍 문제 접근

🧠 수식으로 풀이하기

💡 배운 점

🧮 코딩테스트에서 자주 쓰이는 math 함수 정리

✍️ 정리

[복습] Python 배우기 100~150

[복습] 알고리즘 기초 1/2 201-자료구조1(연습+참고)

0개의 댓글

🧮 코딩테스트에서 자주 쓰이는 `math` 함수 정리