본문 바로가기

백준

14911 궁합 쌍 찾기 많이 안 어려웠다. 이 문제 풀면서 배웠던 거 마구 써먹었음ㅋㅋ 입력 안 정해져있을 때 while (cin >> input) {} 이런 식으로 입력받을 수 있는 거랑, 순서 자동으로 정렬되고 중복 없어야 하니깐 set으로 입력 받는 거랑, set 출력할 때 auto 쓰는거랑 최대 최소 min, max 사용하는 거ㅋㅋ 뿌듯합니다 #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; using i64 = long long.. 더보기
2022 사다리 보자마자 수학문제인 줄 알고 열심히 식 세워보려다가 포기했다. 알고보니 이분탐색으로 c를 찾는 문제였음. 아무튼.. 이분탐색이라는 걸 알아도 너무 어려웠다. 식 만드는 게 특히ㅜㅜ 어느 부분을 탐색할지 정하는 것도 애매하고 c를 구하는 식 세우는 것도 어렵고.. 어찌저찌 구하긴 구했다. 그래도 전에 실수 이분탐색 문제를 풀어봐서 좀 편했다. 그렇습니다 int main() { int n; scanf("%d", &n); vector x(n), v(n); for (int i = 0; i < n; i++) scanf("%lld", &x[i]); for (int i = 0; i < n; i++) scanf("%lld", &v[i]); double lo = 0, hi = 1e9; for (int i = 0; i <.. 더보기
14002 가장 긴 증가하는 부분 수열 4 전까지 푼 LIS 문제가 단순히 길이를 구하는 문제였다면 이번 문제는 해당 수열까지 알아야 한다. 놀랍게도! 작년 알고리즘 수업 시간에 배운 개념이었어서 그걸 응용해서 풀 수 있었다. dp 배열에 최대 길이만 저장하는 게 아니라 자신의 이전 인덱스도 저장한다. 그래서 i번째 배열이 가장 긴 증가수열의 마지막이라 하면, 마지막부터 한 칸씩 되짚어본다. 그럼 해결~~~~ #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; using i.. 더보기
2565 전깃줄 처음에는 전깃줄 두 개 따로 저장한 다음 구했는데 틀려서 고민 엄청 하다가 아래 그림 보니 a를 기준으로 b의 증가하는 수열을 구하면 될 것 같았다. 그래서 pair로 저장한 다음 xx를 기준으로 정렬한 다음 LIS로 구했다. 이 문제가 LIS라서 바로 LIS로 구했긴 한데 증가하는 수열을 고르면 왜 정답이 되는지는 증명하지 못하겠다.. #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; using i64 = long long; u.. 더보기
11053 가장 긴 증가하는 부분 수열 매일 한 문제씩 알고리즘 푸는 스터디.. 약간 구몬 느낌으로 문제 받아서 풀고있다. 저번에는 DP문제를 줘서 풀만했는데 이번에는 LIS라는 듣도보도 못한 알고리즘을 들고와서 힘들었음ㅠ 이리저리 검색해보니 LIS는 최장 증가 수열.. 숫자가 증가하는 부분 수열을 구하는 알고리즘 같다. 완전탐색으로 하면 2^n이 걸리고 DP를 쓰면 N^2이 걸린다. 이분탐색을 써서 최적화를 할 수 있다고는 하는데 이건 나중에 풀어보던가 해야지. #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).e.. 더보기
1149 RGB거리 이것도 디피문제 처음에 단순히 각 단계별 최소값을 구하려 했는데 그러면 놓치는 부분이 분명 있을 것 같아서 고민 좀 했다. 알고보니 색을 따로 저장하면 된다. 현재 색이 빨강일 때 -> 이전 값 중 파랑이랑 녹색 중 최소를 더함 빨, 초, 파 전부 구해주면 완성~~~ #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() #define MAXN 1e6 using namespace std; using i64 = long long; using ii = pair; using i.. 더보기
1463 1로 만들기 아주 살짝 DP가 어떤 느낌인지 알겠다. 배열만들어서 작은 값부터 채워 넣는 것 같구.. (물론 재귀로 해도 되긴 하지만) 값 넣는 건 그리디의 동전 문제 느낌으로 가능한 방법 (3으로 나누기, 2로 나누기, 1 빼기) 중 가장 작은 값 넣으면 된다. 21일 전에 푼 게 내가 푼 건가?? 기미상궁 하는 다른 팀원인가?? #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() #define MAXN 1e6 using namespace std; using i64 = long .. 더보기
1003 피보나치 함수 어.. 어떻게 하지.. 싶다가 피보나치 디피 생각나서 비슷하게 풀었다. ucpc2020 계정으로 기미상궁 할랬는데 실수로 본계정으로 제출했지만 맞아서 다행 ^~^ #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; using i64 = long long; using ii = pair; using ii64 = pair; int main() { int t; scanf("%d", &t); vector v(41); v[0].xx = 1; .. 더보기

티스토리툴바