본문 바로가기
연습장

Row of the odd triangle

by anothel 2022. 2. 14.

Given a triangle of consecutive odd numbers:

             1
          3     5
       7     9    11
   13    15    17    19
21    23    25    27    29
...

find the triangle's row knowing its index (the rows are 1-indexed), e.g.:

odd_row(1)  ==  [1]
odd_row(2)  ==  [3, 5]
odd_row(3)  ==  [7, 9, 11]

Note: your code should be optimized to handle big inputs.

 

Solution

#include <vector>

std::vector<unsigned long long> odd_row(unsigned long long n) {
  std::vector<unsigned long long> vResult;
  unsigned long long c = n * (n-1) + 1;
  
  for(unsigned long long i = 0; i < n; i++) {    
    vResult.push_back(c);
    c += 2;
  }
  
  return vResult;
}

 

남의 코드

#include <vector>

typedef unsigned long long ull;
typedef std::vector<ull> vull;

vull odd_row(ull row) {
  vull v(row);
  ull base = row * (row - 1);
  for (ull i = 0; i < row; i++) {
      v[i] = base + i * 2 + 1;
  }
  return v;
}

 

후기

홀수로 된 삼각형에서 특정 층에 있는 홀수들을 가져오는 문제였다. 규칙을 찾으면 간단했는데 이런 규칙을 찾는 것도 동적 계획법(DP)이라고 할 수 있을까? 그리고 큰 수가 들어올 거라고 Note에 알려주긴 했지만 흠.. 정말로 큰 수가 들어올 수 있게끔 파라미터의 자료형을 바꿔줘야 했다.

 

(url: https://www.codewars.com/kata/5d5a7525207a674b71aa25b5)

 

728x90

'연습장' 카테고리의 다른 글

A+B - 7 - 11021  (0) 2022.02.16
Create Phone Number  (0) 2022.02.15
피보나치 함수 - 1003  (1) 2022.02.13
터렛 - 1002  (0) 2022.02.12
2022 KAKAO BLIND RECRUITMENT > 신고 결과 받기  (0) 2022.01.21