프로그래머스 삼각 달팽이

문제 URL : https://programmers.co.kr/learn/courses/30/lessons/68645

코딩테스트 연습 - 삼각 달팽이

 

문제접근법 :  *를 계단식으로 출력해봤다면 출력자체는 어렵지 않습니다.

하지만 계단식으로 빙빙 돌면서 1부터 채워야합니다. 그렇지만 몇까지 채워야할까요?

 

입력이 n일때 정사각형 2차원배열이라면 n*n까지 채워야하지만

이것은 계단식 삼각형이기에 분명 n*n 이하일수 밖에없습니다.

n=5일때 계단식 채우기

위 그림과같이 계단식으로 숫자를채웠을때 15까지 채워집니다. 만약 다채운다면 25겠지만 10이 줄었습니다.

어떻게 줄었는지 규칙 바로 보이시나요? 붉은색 부분은 윗줄에서 4+3+2+1 =10 즉 거꾸로 보자면

1+2+3+4=10이기에 등차가 1인 수열의합을 구한다면

입니다. 그렇기에 따라서 전부

만큼 채워야합니다.

 

숫자를 몇까지 채우는지 알았다면 인제는 어떻게 채워야하는건지 알아야합니다.

달팽이 모양처럼↓→↖ 방향으로만 반복해서 숫자를 채워주면되고 숫자가 채워지거나 혹은 밖으로 나간다면 방향을

순서대로 바꿔주기만 하면됩니다.

 

소스코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

#include <bits/stdc++.h> using namespace std; int dy[3] = { 1,0,-1 }; int dx[3] = { 0,1,-1 }; int summation(int n) {     return (n * (n - 1)) / 2; } vector<int> solution(int n) {     vector<int> answer;     int finish = n * n - summation(n);     int idx = 0, dir = 0;     int y = 0, x = 0;     vector<vector<int>> v(vector<vector<int>>(n, vector<int>(n, 0)));     while (idx<finish) {         while (0 <= y && y < n && 0 <= x && x < n && !v[y][x]) {             v[y][x] = ++idx;             y += dy[dir];             x += dx[dir];         }         y -= dy[dir];         x -= dx[dir];         dir = (dir + 1) % 3;         y += dy[dir];         x += dx[dir];     }     for (int i = 0; i < n; i++) {         for (int j = 0; j <= i; j++)             answer.push_back(v[i][j]);     }     return answer; } Colored by Color Scripter

cs

궁금한점 혹은 모르는점 어떤 질문이라도 댓글은 언제나 환영입니다.