[Programmers 코딩테스트 고득점 Kit] N으로 표현

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/42895

코딩테스트 연습 - N으로 표현

set을 이용해서 푸는 재밌는 문제였습니다.

set을 이용한 이유는 숫자 중복을 방지하기 위해서입니다.

 

알고리즘은 아래와 같습니다.

1. vector<set<int>>를 정의해주는데 벡터 내 인덱스의 뜻은 N을 사용한 횟수입니다. ex) [1] -> N 1번 사용, [5] -> N 5번 사용

2. 1 ~ 8까지 반복문을 돌리며 1번에서 정의한 벡터의 인덱스에 N으로 i번 이어진 숫자를 넣어줍니다.

2.1 N을 j번 쓴 숫자와 N을 (i - j)번 쓴 숫자에 대해 사칙연산을 진행하면 N을 i번 쓴 숫자를 구할 수 있으므로 해당 조합을 모두 벡터의 i번째 인덱스에 넣어줍니다.

2.2 2.1 과정을 거친 뒤 i번째 인덱스 내 number가 있으면 i를 반환해줍니다.

3. 2번 과정을 모두 거쳤는데도 불구하고 number가 나오지 않아다면 -1을 반환해줍니다.

 

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~