반갑습니다!

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 해당 문제에서는 설치할 기지국의 개수가 중요하다. 어느 지점에 설치하는지는 몰라도 되기 때문에 개수만 구하는 방법으로 해결했다. 이미 설치된 기지국은 크게 3종류로 나눌 수 있다. 첫번째 기지국 마지막 기지국 나머지 기지국 이렇게 3종류로 나눈 이유는 각 기지국 사이에 새로운 기지국을 설치해야하는데, 첫번째 기지국과 마지막 기지국의 전파 도달 거리가 아파트를 벗어날 수 있기 때문이다. 따라서 각각의 케이스를 나눠주었다. 그렇다면 이제 각 기지국 사이에 몇 개의 기지국을 지을 수 있는지에 대해 알아보자. ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제를 처음 봤을 때, C++ 기준으로 next_permutation()을 사용해서 해결할 수 있을 것이라 생각했지만, n이 20이하의 자연수이므로 효율성 테스트를 통과할 수 없다. 해당 문제는 k번째 방법만 알면 되기 때문에 순열의 모든 경우를 구할 필요 없이 해당 경우만 구해주면 된다. k번째 방법은 첫번째 자리 숫자부터 어떤 숫자가 들어갈지 계산을 통해 구할 수 있다. 예를 들어 n이 5이고, k가 107이라고 해보자. 우선 n이 5이므로 줄 서는 방법은 총 5! = 120 가지가 된다. 총 120..

1735번: 분수 합 www.acmicpc.net 풀이 최대 공약수와 최소 공배수를 이용해서 해결하는 문제이다. 분수 덧셈을 하기 위해서 분모들의 최소 공배수를 알아야한다. 최소 공배수를 구하고 나면 분자에 어떤 수를 곱해야하는지를 알 수 있으므로 덧셈 결과를 구할 수 있다. 덧셈이 끝난 뒤 분모와 분자의 최소 공배수를 구해서 기약 분수로 만들어주면 된다. 코드 #include using namespace std; int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int a1, a2, b1, b2; cin >> a1 >> b1; ci..

17213번: 과일 서리 www.acmicpc.net 풀이 중복 조합을 사용해서 해결하면 된다. 이 때 중요한 것은 모든 과일의 종류가 최소한 1개는 포함되어야한다는 점이다. 이를 조심해서 구현하면 된다. 조합을 구현할 때는 동적 계획법을 사용해서 구현했다. 코드 #include using namespace std; int n, m; int comb[41][41]; int combination(int a, int b) { int& ret = comb[a][b]; if (ret != -1) return ret; if (b == 0 || a == b) return ret = 1; return ret = combination(a - 1, b - 1) + combination(a - 1, b); } int ma..

2965번: 캥거루 세마리 www.acmicpc.net 풀이 캥거루 간의 간격을 최대한 길게 유지하면 된다. 예를 들어 캥거루의 위치가 3 5 10 이라면 첫 번째 간격은 2이고 두 번째 간격은 5이다. 따라서 3에 있던 캥거루가 5와 10 사이에 들어가면 되는데, 이 때 그 다음에 다시 점프할 때를 생각해서 계속해서 긴 간격을 유지해야한다. 따라서 5와 10 사이에서 6 또는 9에 점프하게 된다. 5 6 10이라고 하면 그 다음엔 5 캥거루가 7로 점프한다. 이런 방식으로 반복하면 최대 횟수가 된다는 것을 알 수 있다. 따라서 맨 처음 캥거루 사이의 간격의 최대값 - 1이 정답이 된다. 코드 #include #include using namespace std; int main(){ int a, b, c..