tony9402

[문제] 백준 3025 돌 던지기 [알고리즘] 시뮬레이션 [시간복잡도] $ O(N + R) $ [솔루션] 일단 딱봐도 시뮬레이션을 해야한다. 하지만 단순 시뮬레이션으로 소스코드를 짠다면 $ O(NR) $로 무조건 시간초과이다. 이를 어떻게 줄일지 아이디어를 생각해봐야한다. 아이디어 1 : 돌 던졌을때 직선으로 내려가는 부분을 잘 정리하면 시간초과가 해결될 것 같다. 결론부터 말하자면 이것도 시간초과이다. 벽의 분포로 인해 돌이 지그재그로 떨어지는 경우 돌 던지는 경우마다 $ O(R) $을 갱신하기 때문에 TLE이다. 아이디어 2 : 그렇다면 지그재그로 가는 경로도 잘 정리하면 될 것 같다. 이거 또한 $O(R)$의 시간복잡도를 가질 것이다. 따라서 시간초과. 아이디어 3 그렇다면 어떻게 짜야할까? 바로,..

저번 셋을 통해 4문제 2시간이 은근 짧다고 느껴져서 2문제를 추가하여 돌렸다. 총평은 역시 그리디가 많고 언제나 어렵다... [문제] Codeforces 1384 A [문제 유형] Greedy, Constructive algorithms [시간복잡도] $O(n)$ [풀이] 문자열 $S_{i}$와 $S_{i+1}$의 가장 긴 공통 접두사의 길이가 n개 주어진다. 이를 가지고 조건에 만족하는 문자열을 출력하면 된다. [소스코드] #include #define all(x) (x).begin(),(x).end() using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const ll MOD = 1e9 + 7; char nex..

백준에서 알고리즘 풀다가 최근에 다시 코드포스를 참가하면서 느낀점은 CP 실력이 더더욱 나빠졌다는 것이다. 따라서 실력을 상승시키기 위해 난이도를 정해놓고 빠른 시간에 풀 수 있도록 연습을 하려 한다. 처음은 간단하게 난이도 1000 ~ 1400 정도의 문제를 2시간 제한시간을 주고 풀기 시작하고 점차 너무 쉽거나 난이도를 올려도 될때는 문제 수를 늘리거나 난이도를 상향하여 계속 진행할 것 같다. [문제] Codeforces 1385 C [문제 유형] Greedy [시간복잡도] $O(n)$ [풀이] 배열 A에서 A의 접미사 ( $1 \le i \le n, ; [ a_{i} , a_{i+1} , ... , a_{n}]$ ) 중 $a_{i} \le a_{i+1} ... a_{i+k} \ge a_{i+k+1}..

문제링크 : 바로가기 16939번: 2×2×2 큐브 첫째 줄에 2×2×2 루빅스 큐브 각 면의 각 칸 색상이 주어진다. 색상은 1부터 6까지의 자연수로 나타내며, 각 자연수는 총 4번 등장한다. i번째 수가 의미하는 칸은 아래와 같다. www.acmicpc.net 큐브를 한 번만 돌려서 모든 면을 맞출 수 있는지 확인하는 문제이다. 배열 돌리는 연산을 구현하는 것이 살짝 까다롭다. 큐브는 3차원이기 때문에 돌리는 방향은 3가지로 표현 할 수 있다. 전개도를 고정하고 돌릴 수 있는 방향을 써보면 위, 아래( == 위 x3 == -위), 왼쪽, 오른쪽( == 왼쪽 x3 == -왼쪽), 시계방향, 반시계방향(== 시계방향 x3 == -시계방향)이다. 1. 위쪽 방향 2. 왼쪽 방향 3. 반시계 방향 1번에서 ..

1. Triangles (Bronze) 점들을 이용해서 만들 수 있는 모든 직각삼각형 중 넓이가 가장 큰 값을 구하면 된다. #include #define all(x) (x).begin(),(x).end() #define mp make_pair using namespace std; typedef pair pii; vector vc; int cross(int i, int j){ return vc[i].second * vc[j].first - vc[i].first * vc[j].second; } bool check(int i, int j, int k){ pii v1 = mp(vc[i].first - vc[j].first, vc[i].second - vc[j].second); pii v2 = mp(vc[k]...

오랜만에 코드포스를 했다. 6솔 할 수 있었는데 생각하지도 못한 부분 때문에 TLE가 떠서 5솔 밖에 하지 못했다... A. Candies and Two Sisters Problem - A - Codeforces codeforces.com a > 0, b > 0이고 a > b를 만족하는 a + b = n의 개수를 찾는 문제이다. n > 2 일때 b는 1부터 (n - 1) / 2까지 가능하고 n = 1일땐 (n - 1) / 2로 계산 가능하므로 그냥 n을 받으면 (n-1)/2를 출력하는 소스를 짜면 된다. B. Construct the String Problem - B - Codeforces codeforces.com 각 케이스 마다 n, a, b가 주어지는데 n은 문자열의 길이, a는 부분 문자열의 길이..

USACO를 돌면서 공부를 해보려고 한다. 최근 출제된 문제부터 풀 예정이며 실버를 풀면서 적응해 나가며 어려운 문제를 풀 예정이다. 문제를 풀면서 항상 업데이트 할 예정이다. 번호 오름차순으로 보기 번호 내림차순으로 보기

구글 코드잼을 해보았다! (풀이 공개는 대회 끝나고 했습니다.) A ~ E 총 5문제고 30점 이상이면 통과할 수 있다. 30점은 A,B를 다 맞고 C 7점을 긁으면 할 수 있다. E도 풀어보려고 했지만 히든 테케 맞추기 힘들꺼 같기도 하고 그렇다고 긁는것도 귀찮아서 안했다. A. Vestigium 행렬에서 대각선(왼쪽 위부터 오른쪽 아래)의 합을 구하고 행, 열을 보고 한 줄에 중복되는 수가 있으면 개수를 세면 된다. #include #define mp make_pair #define all(x) (x).begin(),(x).end() using namespace std; typedef pair pii; int Map[111][111]; bool visit[111][111], check[111]; in..

USACO를 돌면서 공부를 해보려고 한다. 최근 출제된 문제부터 풀 예정이며 브론즈부터 풀면서 적응해 나가며 어려운 문제를 풀 예정이다. 문제를 풀면서 항상 업데이트 할 예정이다. 번호 오름차순으로 보기 번호 내림차순으로 보기

요즘 DP를 공부하지 않았더니 잘 안풀린다. 그래서 쉬운 문제부터 다시 풀어나가면서 다시 감을 익히려고 한다. DP 공부 및 문제를 풀면서 항상 업데이트 할 예정이다.