pseong

Problem - D - Codeforces codeforces.com 그냥 구현 문젠데 어려워서 정리 잘 관찰만 하면 되는데 그게 어려운 문제 행과 열을 각 각 따로 계산해서 더해줘야 한다. 행에서는 m개의 요소가 계속 돌면서 채워주기 때문에 행 카운트는 항상 단조 증가한다. m개의 요소가 계속 돌기 때문에 만약 안 채워져 있으면 카운트를 1 증가시켜주고 채워주면 된다. 열에서의 관찰이 조금 어려웠는데 일일이 1이 들어오는 경우의 수를 따지다 보니까 굉장히 문제가 어려워졌다. 사실 열에서도 m개의 요소가 사이클을 도는 건 맞지만 한 번 돌 때마다 새로운 m개의 요소가 앞에 추가가 된다. m개의 요소가 사이클을 도니까 m번마다 열 카운트가 반복될 것이다. 반복될 때마다 새로운 요소 한 줄이 맨 앞에 붙으..

F - Ignore Operations AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp dp [i][j] : i개까지 문자를 봤을 때 변환되는 문자의 길이를 j라고 할 때의 경우의 수 라고 놓고 문제를풀면 잘 풀리지만 최적화를 해야 풀린다. 그냥 dp 채우면 O(N^3)이다. 1. 1차원 또는 2차원 또는 3차원 dp 상관없이 dp를 바텀업으로 채울 때 중간에 어떤 연속적인 값을 더하는 구간이 존재한다면 dp를 채우면서 prefix_sum을 이용하면 연속적인 숫자의 방향의 개수에 따라 그 개수만큼 시간 복잡도의 차수를 줄..

F - One Fourth AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 신발끈 공식을 사용하면 한 포인터가 움직일 때마다 계산이 가능하기 때문에 투 포인터로 둘 다 왼쪽부터 탐색하면 될꺼라고 생각했지만 구현에서 조금 문제가 있어서 틀리게 됐다. 중요 포인트는 2가지를 기억하면 된다. 1. 신발끈 공식을 사용하면 맨 마지막 곱셈은 다음 첫번째와의 곱로 넘어가게 되는데 무식하게 그대로 구현했다. 첫번째 점을 원점으로 맞춰주면 더해줄때 마지막 곱셈은 안해도 된다. 이렇게 되면 포인터가 움직일 때마다 크로스곱 한번만 하면 돼..

사실 어려운 알고리즘 중에서 세그먼트 트리만 제대로 쓸 줄 안 다면 정말 정말 편하다. 세그 문제가 아닌데도 세그로 풀리는 문제가 많기 때문이다. 세그먼트 트리만 깊게 파서 나쁠건 없다고 생각한다. 공부 대비 가성비가 정말 좋은 알고리즘 이다. 세그먼트 트리의 구조 세그먼트 트리는 간단하게 부모의 노드가 자손의 노드들 중 리프 노드를 관리한다고 생각하면 된다. 만약 입력값이 1부터 6까지 주어졌다고 생각해보자. 세그먼트 트리의 모양은 아래와 같다. 노드1 : 인덱스 1부터 6까지 관리하는 노드 노드2 : 인덱스 1부터 3까지 관리하는 노드 노드3 : 인덱스 4부터 6까지 관리하는 노드 노드4 : 인덱스 1부터 2까지 관리하는 노드 노드5 : 인덱스 3부터 3까지 관리하는 노드 이렇게 구간을 절반씩 나눠서..

1602A - Two Subsequences 문자열 중에서 아스키코드상 가장 빠른 캐릭터와 나머지 문자열로 나누면 된다. 더보기 #include using namespace std; using ll=long long; using pii=pair; using pll=pair; #define F first #define S second int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; cin >> T; while(T--) { string s; cin >> s; char min_char='z'; int min_idx=0; for(int i=0; is[i]) { min_char = s[i]; min_idx = i; } } cout an[..

1582A - Luntik and Concerts a, b, c가 전부 1개 이상 존재하므로 최대 차이는 1이다. 따라서 차이는 0 또는 1이 될 수 있다. a + b*2 + c*3 이 짝수면 차이는 0이고 홀수면 차이는 1이다. 더보기 #include using namespace std; using ll=long long; using pii=pair; using pll=pair; #define F first #define S second int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T; cin >> T; while(T--) { int a, b, c; cin >> a >> b >> c; int s=a+b*2+c*3; if(s&1)..

1559A - Mocha and Math 어떤 두 수 A, B를 AND 연산을 한다면 항상 그 결괏값은 MIN(A, B) 보다 같거나 작다. 왜냐하면 AND연산은 0은 무조건 0이 되는 마스크 역할을 하고 1은 0 또는 1이 될 수 있기 때문이다. 따라서 다른 숫자와 ADN 연산을 많이 하면 할수록 수는 적거나 같아질 수밖에 없다. 주어진 조건에서 모든 원소를 모든 원소와 AND연산을 할 수 있다. 따라서 정답은 모든 원소를 AND 연산한 값이 된다. 더보기 #include using namespace std; using ll=long long; using pii=pair; using pll=pair; #define F first #define S second int main() { ios::sync_w..

1562A - The Miracle and the Sleeper 30을 예로 들자면 나누는 숫자가 30부터 16으로 작아질수록 나머지는 1 씩 증가한다. 15가 되면 나머지는 다시 0이 되고 나머지는 다시 증가하다가 10이 되면 다시 0이 된다. 이렇게 나머지는 숫자가 점점 커지다가 작아지다를 반복하는데, 잘 보면 나머지의 최대는 대략 30을 2로 나눈 숫자다. 이를 토대로 나눠지는 값은 최대한 크게 잡고 나눠지는 값은 그의 절반값이 될 수 있으면 나머지는 최대가 된다. 하지만, 나누는 값이 나눠지는 값의 절반이 될 수 없으면 나머지는 나눠지는 값 빼기 나누는 값이 된다. 더보기 #include using namespace std; using ll=long long; using pii=pair; usin..