안 쓰던 블로그

[정렬과 이분탐색] 1920 수 찾기 #include #include #include #include using namespace std; vector v; int n; int find(int num) { int s = 0, e = n - 1; while (s > n; for (int i = 0; i > a; v.push_back(a); } //int m; cin >> m; //for (int i = 0; i > a; //auto it = find(v.begin(), v.end(), a); //if (it == v.end()) cout a; cout n; for(int i=0;i> x; a[x]++; //인덱스 증가..

10610 30 #include #include #include #include using namespace std; /* "길거리에서 찾은 수에 포함된 숫자들을 섞어, 30의 배수가 되는 가장 큰 수를 만든다" 처음에 문제를 봤을 때는 주어진 N값을 소인수분해해서 나온 여러 숫자들을 어케 잘 연산해서 30의 배수를 만드는 줄 알았다. 그런데 무한히 더해버리면 무한히 큰 30의 배수를 만들 수 있기 때문에 이건 아니었다 예제를 다시 보니까 "포함된 숫자"라는 의미가 주어진 N의 각각 자리수를 의미하는 것이었다 그리고 각 자리수를 어케 잘 재배치해서 가장 큰 30의 배수를 만들면 된다 30의 배수가 될 조건을 만족하는지 확인하고 각 자리수를 큰 수부터 재배치한다 30의 배수가 될 조건 1. 끝자리가 0 2..

1676 팩토리얼 0의 개수 #include #include #include #include using namespace std; int n, m; /* 2와 5를 곱할 때만 0이 생긴다 5보다 2가 많으니까 5만 세면 된다 근데 5의 배수가 예외 5*2=10 5*5*2*2=100 5*5*5*2^3=1000 2는 충분히 많다고 칠 수 있으므로(소인수분해 하면 2가 잔뜩나온다) 5의 배수는 1개씩 늘 때마다 0의 개수가 1개씩 증가되며 추가된다고 볼 수 있다 5^4=625는 문제 범위인 500을 넘으므로 패스 */ int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; while (n >= 2) { if (n % ..

1 2 3 4 B B 42 B F F 다음과 같이 공백과 숫자(1

문제 설명 입력으로 a, b가 들어오는데, b와 b+1을 잇는 사다리가 a에 있다는 의미 위에 그림으로 보면 2, 3이면 3과 4사이를 잇는 2 위치에 사다리가 있다는 의미임 가로선을 최소로 추가해서 i번 세로선의 결과를 i로 만드는 문제 세로선의 개수는 2> y >> x; map[y - 1][x] = true; //y-1번째 col에서 x~x+1을 잇는 사다리 } go(0, 0); if (res == 1e9) cout

(A,B)로부터 a+=b, b+=a 를 통해 만들어진 수를 (iA+uB, jA+vB) 라고 설정하면 이들의 합 (i+j)A + (u+v)B는 A, B 정수 계수를 갖는 선형결합이므로 배주 항등식에 의해 (i+j)A + (u+v)B = gcd(A,B)가 된다 배주 항등식 0이 아닌 정수 a, b에 대해 d를 a와 b의 최대 공약수라고 하면, 수식을 만족하는 해 (x,y)는 반드시 존재한다 $ax+by=d$ 특히 a와 b가 서로소이고 d=1이라면, 베주의 항등식에 의해 정수해가 반드시 존재한다 확장 유클리드 수식과 완전히 동일하지만, 여기서는 (x,y) 해가 반드시 존재함에 포커싱을 둔다 여기까진 질문탭에 있는 답변이었다. 다르게 생각해 볼까 처음 시작하는 a, b값을 각각 a0 b0이라고 하면, 두 명령을..

그래프에서 사이클 구간 찾는 문제 문제 이해 자체는 쉬운데 구현이 어려웠다 사이클을 찾아야 하는데, 다른 사람들 글을 보니까 finish배열을 써서 finish가 체크가 아닌데 visit는 체크이면 사이클이고 그런다던데 뭔소린지 직관적으로 이해되지 않아서 이해하는 데 좀 걸렸다 1. 사이클 확인 그래서 내 나름대로 이해해 보았는데, finish배열말고 아래처럼 생각하면 좋더라 void dfs(int now) { int next = v[now]; //가리키는 거 if (visit[next]) { //방문을 했던 노드인데 또 탐색하러 오게 되면 사이클이다 //구현 } visit[now] = 1; dfs(next); //다음 경로 } dfs를 돌면서 보통 이렇게 방문을 체크하고, 방문하지 않았으면 dfs를 또..