2292번: 벌집
문제)
위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌을 때, 벌집의 중앙 1에서 N번 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나가는지(시작과 끝을 포함하여)를 계산하는 프로그램을 작성하시오. 예를 들면, 13까지는 3개, 58까지는 5개를 지난다.
입력 :
첫째 줄에 N(1 ≤ N ≤ 1,000,000,000)이 주어진다.
출력 :
입력으로 주어진 방까지 최소 개수의 방을 지나서 갈 때 몇 개의 방을 지나는지 출력한다.
풀이)
이번에도 저번 분해합과 같이 시간초과와 그걸 해결하기 위한 사투 때문에 알고리즘이 꼬이는 문제가 발생했다.
다음은 처음 짠 코드이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
N = int(input())
a = 2 #2번째 칸
jump = 5 #2번째 방부터 7번째 방까지의 거리
box = 2 #최단거리의 벌집 개수
while True:
if a <= N and a+jump >= N:
print(box)
break
else:
a = a + jump + 1
jump += 6 #규칙성
box += 1
N = int(input())
|
cs |
이 경우 내가 한 입력값은 맞았지만 제출했을 경우 시간초과가 떴다.
(나중에 보니 이것도 틀린 코드였음.)
시간 초과를 해결하기 위해 whlie문을 없애고 그나마 range() 함수를 도입했다.
range의 범위를 적당하게 설정하기 위해 N까지의 값으로 설정해놓고, 중간에 정답을 찾는다면 break가 나도록 했다.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
a = 2
jump = 5
box = 2
for i in range(1, N):
if a <= N and a + jump >= N:
print(box)
break
else:
a = a + jump + 1
jump += 6
box += 1
|
cs |
이때부터 틀렸습니다. 만 주구장창 나왔다. 이를 해결하기 위해 열심히 생각해본 결과.
제일 처음의 값을 신경쓰지 못했다는 것을 확인했고 해결하기 위해서 N이 1일때의 경우를 알고리즘에 추가했다.
[정답]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
N = int(input())
a = 2
jump = 5
box = 2
if N == 1:
print("1")
for i in range(1, N):
if a <= N and a + jump >= N:
print(box)
break
else:
a = a + jump + 1
jump += 6
box += 1
|
cs |
출처 : https://www.acmicpc.net/problem/2292
2292번: 벌집
위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌
www.acmicpc.net
'Develop > 백준 (python)' 카테고리의 다른 글
| [백준] 2798번: 블랙잭 (python) (0) | 2022.01.15 |
|---|---|
| [백준] 2775번: 부녀회장이 될테야 (python) (0) | 2022.01.12 |
| [백준] 2231번: 분해 합 (python) (0) | 2022.01.11 |
| [백준] 1259번: 팰린드롬수 (python) (0) | 2022.01.11 |
| [백준] 1085번: 직사각형에서 탈출 (python) (0) | 2022.01.10 |