BOJ-1003
22 Jul 2021
처음에 틀리고, 질문게시판에 들러 슬쩍 답변을 보았는데 이번 문제는 자료형 문제가 아니라, 조합의 점화식을 이용하고, OVERFLOW가 나지 않도록 유의해야하는 문제라는 답변을 보고 잠깐 고민하다가 수월하게 수정할 수 있었다. 그리고 잘 사용할 줄 몰랐던 <utility> 라이브러리의 pair개념도 적용해보기도 했다. 하핫… 😅
평소에 nCr 조합식을 풀때 접근했던 뇌피셜 방식이 있었는데, 이게 이번 문제 푸는데 많이 도움이 되었다. 만약 조합의 정의만 알고 접근했다면 오버플로우 다루는데에 까다로웠을 법도 하다.
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
int comb(int n, int r) {
long long nume = 1, de = 1;
for (int i=r; i>=1; i--) {
nume=nume*n;
n--;
de=de*i;
}
return int(nume/de);
}
int main() {
ios::sync_with_stdio(false);
cout.tie(NULL); cin.tie(NULL);
int T, N, M;
cin >> T;
vector<pair<int, int>> p, t;
for (int i=0; i<T; i++) {
cin >> N >> M;
pair<int, int> q = make_pair(N,M);
t.emplace_back(q);
}
for (int i=0; i<T; i++) {
pair<int, int> q = (t.back());
t.pop_back();
p.emplace_back(q);
}
for (int i=0; i<T; i++) {
int count = 0;
int n = p.back().second;
int r = p.back().first;
if (0<r<=n && r<=n<30) {
if (n==r) count = 1;
else {
if (r>n/2) r = n-r;
count = comb(n, r);
}
p.pop_back();
cout << count << endl;
}
}
return 0;
}
오랜만에 수학(?) 문제 푸니까 재밌었고, 풀면 풀수록 오기가 생겼는데 그래서 너무 재밌게 풀었다. 간만에 뇌가 말랑해진 것 같은 느낌?!?@ 허허…^_ㅠ! 🧠🧠
long long과 같은 데이터타입과 문제마다 필요한 값 define이 아직까진 서툴고 낯설다. 어떻게 저렇게 생각해서 풀었지…싶은 너무 대단한 분들이 많다ㅠㅠ!! 스펀지처럼 흡수하는 수 밖에… 🙏🏼😭😭
#include<iostream>
#define MAX 201
#define Moduler 1000000000
using namespace std;
int N, K;
long long DP[MAX][MAX];
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> K;
for (int i = 0; i <= N; i++){
DP[1][i] = 1;
}
for (int k = 2; k <= K; k++) {
for (int n = 0; n <= N; n++) {
for (int i = 0; i <= n; i++) {
DP[k][n] = DP[k][n] + DP[k - 1][i];
}
DP[k][n] = DP[k][n] % Moduler;
}
}
cout << DP[K][N] << endl;
return 0;
}
내일은 월간 밋업이 있는 날인데 밋업에 짧은 GCE 발표 소개를 하게되었는데 준비를 하나도 못했다… 방금까지 슬라이드 만드느라 고생했다… 생각보다 한시간이면 끝날 줄 알았는데 사소한 디자인부터 내용 정리에 자료 검색까지 생각보다 시간이 많이 걸려서 힘들었다ㅜㅜ 세시간반정도 걸렸는데… 그래서 내일까지 해야하는 많은 것들을 다 못했다… 오늘 잠은 글렀다(이러면서 잘잠 ㅠㅠ)(왜 머리가 아프냐…)
Recursion을 사용해 아주 느린 코드… 🤦🏼♀️🤦🏼♀️
#include <iostream>
using namespace std;
int Answer, N;
void collect(int* arr, int* cmp, int j) {
int i = arr[j];
cmp[j] = 0;
if (i+j>N) return;
else if (cmp[i+j]==0) {
Answer--;
return;
}
else if (i<=N) {
collect(arr, cmp, i+j);
}
else return;
}
int main(int argc, char** argv)
{
int T, test_case;
setbuf(stdout, NULL);
cin >> T;
for(test_case = 0; test_case < T; test_case++)
{
Answer = 0;
/////////////////////////////////////////////////////////////////////////////////////////////
cin >> N;
int *arr = new int[N+1];
int *cmp = new int[N+1];
arr[0] = 0; cmp[0] = 0;
for (int i=1; i<=N; i++) {
int num;
cin >> num;
if (num<=0 || num>N) return 0;
else {
arr[i] = num;
cmp[i] = num;
}
}
for (int i=1; i<=N; i++) {
if (cmp[i]==0) continue;
else {
collect(arr, cmp, i);
Answer++;
}
}
/////////////////////////////////////////////////////////////////////////////////////////////
// Print the answer to standard output(screen).
cout << "Case #" << test_case+1 << endl;
cout << Answer << endl;
delete[] arr;
delete[] cmp;
}
return 0;//Your program should return 0 on normal termination.
}
오늘 3시까지 마감이었던 예선이었는데 깜빡하고 오늘 1시쯤 시작해서 한문제밖에 못 풀었다… 성능/테크닉 관점에서 고려도 못한채, 아직까진 실력이 부족하다는 것을 느끼고, 앞으로 체계적으로 난이도 있는 문제 위주로 공부를 시작해야겠다.
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int dp[1001][1001] = {0};
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
string st1, st2;
scanf("%s %s", &st1, &st2);
for(int i=1; i<=st2.size(); i++) {
for (int j=1; j<=st1.size(); j++) {
if (st2[i-1] == st1[j-1])
dp[i][j] = dp[i-1][j-1] + 1;
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
cout << dp[st2.size()][st1.size()] << endl;
return 0;
}
런타임(Segmentation)에러 + 시간초과 에러 발생했었음…. 뭐지…왜지…