joseph0528 코딩 블로그

solved.ac 티어 : 골드 2 www.acmicpc.net/problem/7894 7894번: 큰 수 많은 어플리케이션은 매우 큰 수를 사용한다. 이러한 어플리케이션은 데이터를 안전하게 전송하고, 암호화하기 위해서 수를 키로 사용한다. 수가 주어지면, 그 수의 팩토리얼의 자리수를 구하 www.acmicpc.net 이문제는 log10(1)+log10(2)+log10(3)... log10(m) 이 답인데 처음에 그냥 2중 반복으로 하면 시간 초과 날 거 같아서 log10(1)+log10(2)+log10(3)... log10(m) = log10(m!)인걸 이용해서 팩토리얼을 최대한 짧게 구해서 하려고 했지만 O(M/2)만큼 걸려 시간 초과가 나서 그냥 2중 반복으로 했더니 맞았다;; import math..

solved.ac 난이도 :플래 3 www.acmicpc.net/problem/12844 12844번: XOR 크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다. www.acmicpc.net 이문제는 일반 세그 레이지에서 +를 XOR(^)로 바꿔주면 된다. 하지만 이렇게만 바꿨을 경우 틀리게 된다. tree[n]=lazytree[n]*(e-s+1); 이거를 if((e-s+1)%2!=0){ tree[n]^=lazytree[n];//*(e-s+1); } 이렇게 바꿔주면 된다. 저렇게 바꿔 주는 이유는 어떤수를 a라고..

solved.ac 티어 : 플래티넘 4 www.acmicpc.net/problem/1574 1574번: 룩 어택 첫째 줄에 체스판의 크기 R과 C가 주어지고, 빈 칸의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 빈 칸의 좌표가 주어진다. 좌표는 (행, 열)의 형태로 주어지고, 가장 윗 행은 1번 행이고, 가장 왼 www.acmicpc.net 이문제는 한 행 과열에 단 한 개의 룩을 놔서 최대한 많이 놓은 개수를 출력하는 문제이다. 정말 간단한 이분 매칭 문제다. 행과 열에 한 개만 놓을 수 있다는 것은 행 또는 열을 잡고 자신이 놓을 수 있는 곳에 이분 매칭을 해주면 된다. 하지만 여기서 빈칸이 생기는데 그래도 공격이 막히지는 않으니 입력 위치가 아니면서 놓을 수 있는 곳들을 이분 매칭 해주면 된다...

solved.ac 난이도 : 플래 5 www.acmicpc.net/problem/2505 2505번: 두 번 뒤집기 첫줄에는 숫자판의 크기를 나타내는 정수 N (5≤N≤10,000)이 주어진다. 그 다음 줄에는 두 개의 구간이 뒤집혀진 놀이판의 상태를 나타내는 숫자들이 하나의 공백을 두고 나타난다. www.acmicpc.net 이 문제의 풀이는 의외로 간단하다. 이문제 조건에서 한 번만 뒤집는다고 바꿨을 때 어떻게 하면 구할 수 있을까? 한 번만 뒤집는 경우 해당 값이랑 해당 위치가 다를 경우 해당 위치랑 같은 값을 찾아서 반전을 시켜주면 된다. 이걸 두 번 뒤집기에 똑같이 적용해서 값이 다를 경우 찾아서 바꿔주면 된다. 하지만 이렇게 했을 경우 반례가 생긴다. 하나의 예를 들어보면 10 1 8 7 6 ..

solved.ac 난이도: 골드 3 www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 이문제를 그냥 2중 반복으로 풀면 시간 초과가 무조건 뜬다. import sys input=sys.stdin.readline a=int(input()) l=[0]*(10000001) t=list(map(int,input().split())) o=0 for i in range(a):l[t[i]]+=1 for i in range(a): o=0 for g in range(i+1,a): if l..

solved.ac 난이도 :골드 4 www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 이문제를 풀려면 지문을 잘 이해해야 된다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다. 이 말은 이문제는 단방향 그래프라는 거고 b에서 a로 간다는 말이 된다. 그러므로 입력으로 a, b가 주어졌을 때 다익스트라 코드에 a에서 b가 아닌 b에서 a로..

solved.ac 티어 : 플래티넘 5 www.acmicpc.net/problem/18138 18138번: 리유나는 세일러복을 좋아해 너비가 3인 티셔츠와 너비가 2인 세일러 카라를 붙이고, 너비가 5인 티셔츠에 너비가 5인 세일러 카라를 붙이고 너비가 7인 티셔츠에 너비가 4인 세일러 카라를 붙이고 너비가 10인 티셔츠에 너비 www.acmicpc.net 이문제는 아주 쉬운 이분 매칭이라 입력을 받고 너비가 w/2 이상 w*3/4 이하랑 너비가 w 이상 w*5/4인 경우 해당 위치에 값을 넣어주고 이분 매칭 하면 끝난다. (이 문제 못 풀면 이분 매칭 다시 배워야 된다.) #include #include #include #include #include using namespace std; typedef..

세그 레이지를 이용했습니다. solved.ac 티어 : 다이아 5 www.acmicpc.net/problem/19851 19851번: 버거운 버거 드디어 산업기능요원 복무를 마친 키파는 버거운 직장에서 벗어나 새로운 직업에 도전하고자 햄버거집을 차렸다. 키파는 케이크를 여러 차례 만들면서 빵은 좀 구워 봤지만 햄버거를 만드는 것 www.acmicpc.net 이문제는 금광세그로 하는 풀이도 있지만 세그 레이지로 풀이하겠다.. 풀이는 구간에서 남는 )의 개수와 (의 개수를 구하는 방식이다. 배열에 원래 구간과 반전했을때의 구간을 저장하고 변경이 일어날 때마다 2개의 구간을 반전시키면서 바꿔준다. 처음에 트리를 만들때 struct으로 트리안에 배열을 넣어서 트리를 만든다. void seg(ll n,ll s,l..

이분 매칭 문제입니다. solved.ac 티어 : 플래티넘 3 www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 그룹지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 www.acmicpc.net 이문제는 입력받은 것을 2중 반복하면서 자신이랑 위치가 다른 곳 중에서 둘이 더했을 때 소수일 때만 배열에 넣어주고 배열에서 첫 번째 위치의 배열에 들어있는 수 개수만큼 반복하면서 첫 번째 수랑 더했을 때 소수가 되는 수들이랑 첫 번째 수를 하나하나 빼면서 나머지 수들로 전부다 짝이 만들어질 경우 배열..

세그먼트 트리 min,max를 이용한 풀이입니다 solved.ac 티어 : 플래티넘 3 www.acmicpc.net/problem/9345 9345번: 디지털 비디오 디스크(DVDs) 손님이 DVD를 카운터에 가져왔을 때 손님이 원하는 DVD가 전부 존재하면, (A번 선반부터 B번 선반까지에 있는 DVD를 전부 가져왔을 때 순서에 상관없이 A번 DVD부터 B번 DVD까지 있다면) "YES"를 출력하 www.acmicpc.net 이 문제를 풀려면 구간의 최솟값과 최댓값을 구해야합니다 그 이유는 만약 A가 1부터 4까지의 구간의 책을 가지고 왔습니다. 이때 1부터 4까지의 책들이 순서는 상관없이 모두 있어야합니다. 만약 1부터 4까지의 최솟값이 1이 아니라면 1보다 작은 값이 들어있거나 1은 들어있지 않게 ..