[백준] 1193번 분수 찾기(파이썬)

오늘은 학교에서 2주 동안 푸는 알고리즘 챌린지에서 가져와봤다.

9일 차 초보 단계인데

 

 

이렇게 주어졌다. 

처음에 딱 접했을 때, 언뜻 봤을 때 간단해 보였는데 이게 또 막상 풀어보려 하니까 머리가 잘 안 돌아갔다.

그래서 생각해 낸 방법은 일단 위와 같은 표로 보기엔 너무 헷갈려서 대각선 한 줄마다 한 라인이라고 생각하고 

각 라인의 첫 번째와 마지막 숫자의 위치를 알아냈다. 

 

 

우선 전체적인 코드를 보면 이렇게 된다.

x = int(input())
count = 0
max_count = 0
dic = {}

while x > max_count: # 입력된 값이 라인 끝 수보다 클 때까지
  count += 1
  max_count += count  # 1+2+3+4+5+6+7,,, 해당 라인마다 더해준다.
  
init_count = max_count-(count-1) #해당 라인의 첫번째 숫자

if count % 2 == 1: # 분모 : 오름차순, 분자 : 내림차순
  for i in range(1,count+1):
    dic[init_count] = (count-(i-1))/i
    if x == init_count:
      print("{0}/{1}".format(count-(i-1),i))
    init_count += 1
    
else:              # 분모 : 내림차순, 분자 : 오름차순
  for j in range(1,count+1):
    dic[init_count] = j/(count-(j-1))
    if x == init_count:
      print("{0}/{1}".format(j,count-(j-1)))
    init_count += 1

 

이제 코드를 분석해 보면

x = int(input())
count = 0
max_count = 0
dic = {}

우선 어느 위치의 수를 알고 싶은지 입력해 주는 x값과 

라인을 나타내는 count,

해당 라인의 가장 마지막 수를 나타내는 max_count,

그리고 딕셔너리를 하나 선언해주었다.

 

while x > max_count: # 입력된 값이 라인 끝 수보다 클 때까지
  count += 1
  max_count += count  # 1+2+3+4+5+6+7,,, 해당 라인마다 더해준다.
  
init_count = max_count-(count-1) #해당 라인의 첫번째 숫자

입력된 x값이 max_count보다 클 경우 

라인수를 1씩 추가해 주고 이 라인을 max_count에 더해주었다.

이렇게 되면 max_count는 등차수열처럼 1씩 계속 커진 상태로 더해지는 모습을 볼 수 있다.

 

이때 입력된 x값이 max_count와 같은 순간이 오게 되면 while문은 끝나게 된다.

 

그리고 해당 라인의 첫 번째 수인 init_count도 계산을 통해 구해주었다. 

 

마지막 코드를 보면,

if count % 2 == 1: # 분모 : 오름차순, 분자 : 내림차순
  for i in range(1,count+1):
    dic[init_count] = (count-(i-1))/i
    if x == init_count:
      print("{0}/{1}".format(count-(i-1),i))
    init_count += 1
    
else:              # 분모 : 내림차순, 분자 : 오름차순
  for j in range(1,count+1):
    dic[init_count] = j/(count-(j-1))
    if x == init_count:
      print("{0}/{1}".format(j,count-(j-1)))
    init_count += 1

 

우선 라인이 홀수, 짝수에 따라 분모와 분자의 규칙이 달라지기에 if문을 써서 홀, 짝을 우선적으로 구분해 주었다.

 

라인이 홀수일 경우에는 분모가 오름차순, 분자는 내림차순이고

라인이 짝수일 경우에는 반대로 분모가 내림차순, 분자는 오름차순이다.

 

이 오름, 내림차순을 어떻게 처리를 해 줘야 하나 고민하다가 for문을 통해 분자나 분모를 우선 해결해주고 count와 i값을 통해 나머지 부분도 해결해주었다. 

각 위치마다 계산된 수를 딕셔너리로 넣어줬는데 막상 코드를 완성시키고 보니 이 부분은 필요 없었던 것 같다. 

 

라인의 첫 번째 수를 1씩 계속 증가시켜준 다음,

만약 입력된 x값이 init_count와 같아질 경우 해당 위치의 결과값을 출력문에 맞게 출력해 주었다. 

끝!