[CLASS 2]백준 2231번, 2292번, 2775번

2231번 : 분해합

 

간단하다. N을 받고, 1부터 N-1까지 자릿수를 모두 더해 보면서 만약 N 과 일치한다면 바로 출력하고 종료하면 된다.

 

내 코드:

n = int(input())
answer = 0
for i in range(n):

    h = sum([int(i) for i in str(i)]) + i

    if(h==n):
        answer = i
        break

print(answer)

 

브루트 포스법. 즉 전수 조사이다. 그냥 하면 된다.

 

2292번 : 벌집

 

 

처음 보고 띠용? 하고 가만히 있었는데, 풀고 나니 그렇게 어려운 문제는 아니었다. 육각형의 각 껍질에서의 가장 마지막 수를 얻을 수 있는 수열을 만들고 적용하면 된다.

 

그래서 처음엔 이렇게 제출했다.

 

내 코드(오답):

def f(n):
    return 6*((n*n+n)/2+1)-5

p = int(input())

i = 0
while(True):
    if(f(i-1) < p and p <= f(i)):
        print(i+1)
        break
    i += 1

간단하지만 단순무식한... 그런 코드이다. 결과는 시간 초과.

 

이 코드의 가장 큰 문제점은 연산을 불필요하게 2번씩 한다는 점이다.

 

f(-1) 과 마지막 f(i) 를 제외하면 겹치는 구간이어서 같은 연산을 두 번씩 하기 때문에 시간 초과가 뜬 것으로 보인다.

 

그래서 코드를 수정했다.

 

내 코드:

def f(n):
    return 6*((n*n+n)/2+1)-5

p = int(input())

i = 1
li = [0]
while(True):
    li.append(f(i-1))
    if li[i-1] < p and p <= li[i]:
        print(i)
        break
    i += 1

 

아까와 비슷하지만 달라진 점은. 리스트에 계산값을 저장한다는 것이다. 이러면 쓸데없는 계산을 안하게 되고, 최종적으로 계산 량이 아까의 거의 절반이 된다.

 

더 나은 코드:

n = int(input())
answer = 1
for i in range(1,n+1):
	answer += (i-1) * 6
	if answer >= n:
	    break

print(i)

 

더욱 간단한 해결책이 있다. 각각의 껍질은

• 1번껍질(중앙) -> 1개
• 2번껍질 -> 6개 ( 누적 1 + 6)개
• 3번껍질 -> 12개 (누적 1 + 6 + 12)개
• 4번껍질 -> 18개 (누적 1 + 6 + 12 + 18)개
•  
• 즉 n 번껍질 -> 6n-6개 (누적 1+ ... + 6n-6)개 이다.

이를 수학적으로 공식을 세워서 푼 것이 내 코드이고, 좀더 프로그래밍적? 으로 푼 것이 아래의 코드이다

 

for 문을 실행하는데, 실행 시마다 answer 에 6씩 늘어나는 값을 더해준다.

 

그러다가 answer가 N을 넘어서는 순간의 i 값이 바로 해당 껍질 번호이다.

 

만약 answer 와 n 이 같다면 해당 껍질의 가장 큰 수일 것이다.

 

공식 세워서 하는 것보다는 아래의 방법이 더 나은 것 같다.

 

2775번 : 부녀회장이 될테야

 

이상한 규칙이 있는 아파트에서 특정 층에 사는 사람의 수를 맞추는 문제이다.

 

처음에 재귀로 간지나게 풀어보려고 별 헛짓거리를 다 했는데 지금의 내 머리로는 도저히 불가능할 것 같아서 그냥 for문을 이용하여 풀었다.

 

재귀도 괜찮을꺼 같은데...

 

내 코드:

count = int(input())
k = []
n = []
for _ in range(count):
    k.append(int(input()))
    n.append(int(input()))

room = [[0 for roomNum in range(max(n)+1)] for floor in range(max(k)+1)]
for i in range(max(n)+1):
    room[0][i] = i

for floor in range(1,max(k)+1):
    for roomNum in range(1,max(n)+1):
        room[floor][roomNum] = room[floor-1][roomNum] + room[floor][roomNum-1]

for result in range(count):
    print(room[k[result]][n[result]])

a 층 b 호에 사는 사람 수 = a-1층 b호에 사는 사람 수 + a층 b - 1호에 사는 사람 수

 

이를 이용하면 풀 수는 있다.

 

alcks12님의 코드:

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    k = int(input())
    n = int(input())

    people = [i for i in range(n + 1)]

    for i in range(k):
        for j in range(1, n + 1):
            people[j] = people[j] + people[j - 1]

    print(people[-1])

 

사실 층을 일일이 만들지 않고 1차원 배열을 만든 뒤, 계속 층을 갱신하는 방법이 더 좋다.

 

모든 연산이 끝난 후 가장 오른쪽 인덱스의 값이 해당 방의 인원이다.

 

 

뭔가 쉬운문제를 너무 어렵게 생각해서 푸는것 같다....