넘치게 채우기
[프로그래머스] 유전법칙 (PCCP 모의고사 #1 3번) 본문
https://school.programmers.co.kr/learn/courses/15008/lessons/121685
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
프로그래머스 - 유전법칙(PCCP 모의고사 #1 3번)
문제 유형 : 구현, 수학, 재귀
문제 난이도 : Level 2(개인적인 체감)
문제 설명
멘델은 완두콩을 이용하여 7년간 실험한 결과, 다음과 같은 특별한 법칙을 발견하였습니다.
- 둥근 완두 순종(RR)을 자가 수분, 즉 같은 유전자끼리 교배할 경우, 다음 세대에 둥근 완두 순종 형질만 나타난다.
- 주름진 완두 순종(rr)을 자가 수분할 경우, 다음 세대에 주름진 완두 순종 형질만 나타난다.
- 두 순종을 교배한 잡종(Rr)을 자가 수분할 경우, 다음 세대의 형질은 RR:Rr:rr=1:2:1의 비율로 나타난다. (아래 그림 참조)
![](https://blog.kakaocdn.net/dn/bzsxNW/btsBFoEoWkx/gDgtrepYq4ujhd8K4PF8f0/img.png)
멘델의 법칙을 공부한 진송이는, 직접 완두콩의 자가 수분 실험을 진행했습니다. 진송이의 실험에서 완두콩 한 개를 자가 수분한 결과는 다음과 같습니다.
- 각 완두콩은 자가 수분해서 정확히 4개의 완두콩 후손을 남긴다.
- 잡종 완두콩(Rr)은 자가 수분해서 첫째는 RR, 둘째와 셋째는 Rr, 넷째는 rr 형질의 후손을 남긴다.
- 순종 완두콩(RR, rr)은 자가 수분해서 자신과 같은 형질의 후손을 남긴다.
잡종 완두콩(Rr) 1대부터 시작한 가계도로 그려보면 그림 2와 같습니다.
![](https://blog.kakaocdn.net/dn/QUjrg/btsBKiinDZo/YTZKjZtxkujUQnyFu5nNok/img.png)
진송이는 이러한 완두콩의 자가 수분 실험 결과를 정리하고 싶어합니다. 하지만, 세대를 거듭할수록, 완두콩의 수가 너무 많아져 모든 가계도를 기록하기 어려워졌습니다. 진송이는 가계도를 전부 기록하는 것 대신, 완두콩의 세대와 해당 세대에서 몇 번째 개체인지를 알면 형질을 바로 계산하는 프로그램을 만들려 합니다.
각 세대에서 맨 왼쪽 개체부터 첫 번째, 두 번째, 세 번째, ...개체로 나타냅니다. 예를 들어 그림 2에서 2세대의 네 번째 개체의 형질은 "rr"이며, 3세대의 9번째 개체의 형질은 "RR"입니다.
형질을 알고 싶은 완두콩의 세대를 나타내는 정수 n과, 해당 완두콩이 세대 내에서 몇 번째 개체인지를 나타내는 정수 p가 2차원 정수 배열 queries의 원소로 주어집니다. queries에 담긴 순서대로 n세대의 p 번째 개체의 형질을 문자열 배열에 담아서 return 하도록 solution 함수를 완성해주세요.
풀이
개체 번호의 4를 나눈 몫은 부모의 개체 번호를 나타낸다.
n-1번 반복하여 맨 위 부모까지 거슬러 올라간다.
이 과정에서 한 번이라도 부모의 개체가 "RR"또는 "rr", 반드시 찾으려는 개체는 RR또는 rr이다.
그렇지 않다면 Rr이다.
코드
C++
#include <bits/stdc++.h>
using namespace std;
string getTrait(vector<int> query) {
int gen = query[0];
int idx = query[1]-1;
stack<int> st;
for(int i = 1; i < gen; i++) {
//cout << idx%4 << " ";
st.push(idx%4);
idx /= 4;
}
//cout << endl;
string trait = "Rr";
while(!st.empty()) {
if(trait == "rr" || trait == "RR") break;
if(st.top() == 0) trait = "RR";
else if(st.top() == 3) trait = "rr";
else trait = "Rr";
st.pop();
}
return trait;
}
vector<string> solution(vector<vector<int>> queries) {
vector<string> answer;
for(const auto &query : queries) {
answer.push_back(getTrait(query));
}
return answer;
}
'PS > Programmers' 카테고리의 다른 글
[프로그래머스] 실습용 로봇 (PCCP 모의고사 #2 1번) (0) | 2023.12.10 |
---|---|
[프로그래머스] 운영체제 (PCCP 모의고사 #1 4번) (0) | 2023.12.10 |
[프로그래머스] 체육대회 (PCCP 모의고사 #1 2번) (0) | 2023.12.09 |
[프로그래머스] 외톨이 알파벳(PCCP 모의고사 #1 1번) (0) | 2023.12.09 |
[프로그래머스] 아날로그 시계 (PCCP 기출문제 3번) (0) | 2023.12.06 |