나 요리학원 출신임

과제를 하루에 하나씩 할 수 있고 , 데드라인과 받을 수 있는 점수를 알려준다이 때 점수의 최댓값을 구하는 문제!흔히 볼 수 있는 dp문제다 우리는 과제를 하나하나 보며 선택하면 된다! d[N(n번째 과제)][T(현재시간)]로 테이블을 잡는다 기본값은 과제를 안하고 넘어가는 값으로 잡는다그리고 만약 현재의 과제 데드라인보다 시간이 작다면 과제를 하는것과 비교한다! 소스코드12345678910111213141516171819202122232425#include #include #include #include using namespace std;int n,d[1010][1010];vector vt;int go(int pos, int t) { if (pos == n || t > 1000) return 0; i..

숫자가 주어질 때 오름차순으로 만들려 한다숫자 두개를 swap 가능할 때 최소의 swap 수를 구하면 된다 입력받은 숫자를 정렬시켜서 있어야 할 자리가 맞는지 2중 for문으로 확인하고 제출했다 근데 바로 틀렸따 ㅎㅎㅎ 고민하다가 그냥 생각없이 뒤에서부터 확인하니까 답보다 1이 크게나왔다똑같이 나올 줄 알았는데...그래서 어떤수에서는 앞에서부터 보는거보다 뒤에서부터 보는게 작겠구나~ 생각하고 앞에서부터 비교한 답 & 뒤에서부터 비교한 답을 비교해서 작은답을 출력하니 맞았다! 소스코드12345678910111213141516171819202122232425262728293031#include #include #include using namespace std;int n;int check(vector&a, ..

유저가 N명이 있고 각자의 비밀번호가 주어진다이 때 내 비밀번호가 다른사람의 substring이라면 나의 비밀번호를 입력해서 그 사람의 계정으로 접속이 가능하다..! 문제는 모든 사람에 대해 본인의 계정을 제외한 접속가능한 다른계정의 수를 모두 찾는 것이다! set과 map을 이용하면 풀 수 있는 문제지만 결국 못풀었다 ㅎㅎ쉬운문젠대 왜 생각을 못했을까...! set,map마스터 해야겠다 푸는 방법은 비밀번호를 입력받으며 set에 substring을 다 넣는다그리고 map에서 substring의 수를 +1해준다모든 비밀번호에 대해 수행하고 마지막에 그 수를 더하고 n만큼 빼면(본인계정접속 수) 접속 가능한 다른사람계정 수가 나온다 소스코드1234567891011121314151617181920212223..

이항계수 4까지왔다...!4에서는 대체 뭘 배울수 있을까 바로 뤼카의 정리다...! - 뤼카의 정리위키에는 이렇게 적혀있다 증명을 이해하려했지만 불가능 그래서 난 뤼카가 정리해준것만 받아먹을 예정이다정리하자면 nCr(mod d)가 있을때n과 r을 d진법으로 나타낸다 이 때 nCr = 모든 niCri의 곱(0

제목 그대로 이항계수와 쿼리다쿼리를 날리는대로 뱉으면 된다 다만 팩토리얼을 계속 계산하지말고 미리 저장해둬야한다그럼 바로 가져다가 쓰면됨! 소스코드123456789101112131415161718192021222324252627282930#include #include #include using namespace std;#define ll long longll mod = 1e9 + 7, n, m, k, arr[4000010];ll mypow(ll a, ll b) { if (!b) return 1; if (b & 1) return (a*mypow(a, b - 1) % mod) % mod; return mypow((a*a) % mod, b / 2) % mod;}int main() { scanf(" %lld"..

최대값이 T이고 +A,+B가 가능하다추가로 한번 /2를 할 수 있다 이때 얻을 수 있는 최대값을 구하는 문제다 나누기는 내가 가질 수 있는 최대값에서 나누는게 최적이다그래서 pq를 이용해서 문제를 풀면 된다 pq에 {(나누기 가능여부, 값)}를 넣고 쭉 돌려보면된다!이때 진짜 +A,+B를 하면 시간초과가 나니까A,B를 넣을 수 있는만큼 최대로 넣고 돌면된다! 소스코드12345678910111213141516171819202122232425#include #include #include using namespace std;#define ll long longint t, a, b,ans;bool check[5000050][2];int main() { scanf(" %d %d %d", &t, &a, &b); ..

문제는 남자 n명 , 여자 m명 (n>=m) 일 때 nCm % mod를 구하는 문제다 nCm = n! / m!(n-m)! 인데 여기서 바로 %mod를 해버리면 답이 안나온다 우리는 페르마의 소정리를 사용해서 문제를 풀어야 한다! 페르마의 소정리 ==> p가 소수이고 a와 p가 서로소 일 때 a^p=a(mod p) 가 성립한다 a*a'=1(mod p) 일때 a'가 역원이라고 하자이 때 페르마의 소정리에 의해 a^(p-1) = 1(mod p) 가 성립한다그럼 a*a^(p-2) =1(mod p)가 되므로 역은 a^(p-2)다!! 그럼 a/b = a/b*b*b' = a*b' = a*b^(p-2) 가된다~!b^(p-2)는 log시간만에 구하면 시간초과에서 피할 수 있다! 소스코드1234567891011121314..

전에 weeklyps 에서 트리의 지름을 공부할 배운 방법을 이용했다!자세한 설명은 weeklyps에 있는 트리의 지름을 보는게 빠를듯.. ㅎㅎㅎ 정점 x를 기준으로 x의 서브트리에 속하는 최장거리, 안속하는 최장거리를 구해서 비교해주면 far 배열을 채울 수 있다..! 서브트리 속하는건 쉬워서 바로 구할 수 있다 트리의 깊이를 구하듯이 구하면 된다 속하지 않는 경우에는 다시 또 경우를 나눠서 구하면 된다...!자세한 설명은 weeklyps 꼭 가보시길..! 저도 3번읽음 ㅎㅎ다들 열공~~! 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #includ..

나무를 심는 비용을 다~~ 구해서 곱하는 문제다비용은 지금 심는 나무와 현재 심어져있는 모든 나무까지의 거리의 합이다 이 문제는 펜윅트리를 2개 만들어서 풀 수 있다 하나는 나무가 (0~200000) 중 몇번째 좌표에 몇개가 있는지 아는 용도고두번째는 (나무의 거리 X 수) 를 담아두는 트리다 어떤 좌표 X에 나무를 심는다고 가정하면 우리는 비용을 2가지 작업으로 구할 수 있다. 1) X보다 큰 좌표에 나무가 심어져 있을 때 = (심어진 나무의 거리 합) - (현재 좌표)X(심어진 나무의 수) 2) X보다 작은 좌표에 나무가 심어져 있을 때 = (현재 좌표)X(심어진 나무의 수) - (심어진 나무의 거리 합) 이렇게 하면 비용을 구할 수 있다!트리로 만들어 두면 시간안에 충분히 할 수 있다!근데 문제를 ..

중앙값은 말 그대로 중앙에 있는 값이다K개 중에서 (K+1)/2번째 에 있는 값을 구하면 된다 이 문제는 세그먼트트리로 풀 수 있다.온도가 0~65536 까지니까 넉넉하게 66666까지 잡고온도가 측정될 때 마다 tree에서 온도를 +1 해준다그리고 K개 이상이면 i-k번째를 -1 하고 중앙값을 찾는다! - 세그먼트트리에서 K번째를 찾기 위해서는 나의 왼쪽 자식인 tree[node*2]와 값을 비교해보면 된다만약 K가 같거나 작다면 왼쪽에 있는 것이니까 왼쪽으로가고아니라면 오른쪽으로 가는데 K에서 왼쪽만큼을 빼고 가야한다!그래야 전체적으로 볼때 K번째를 찾을 수 있다. 소스코드123456789101112131415161718192021222324252627282930313233343536373839404..