본문 바로가기

전체 글195

# Bitmap # 문제 # 입력 및 출력 # 풀이 처음엔 재귀를 돌 때 size로 돌게 했었다. 근데 시간초과가 뜨길래 조건문을 걸어서 필요한 부분만 보면 되나 했지만 출력을 위해선 전부 돌아야 하기 때문에 문제가 없어 보였다. 그래서 일단 재귀함수의 파라미터를 size가 아닌 인덱스 값으로 주고 start x, start y, end x, end y 값을 사용해서 돌도록 했다. 해당 문제가 백준에도 있어서 백준에서 먼저 문제를 풀었다. 근데 백준에서는 맞는 답이 espa에서 돌리니까 시간 초과가 떴다. 그래서 fstream 관련해서 시간 초과 문제가 있는지 찾아봤다. 중요한 점 fstream을 사용했는데 해당 파일 입출력 라이브러리가 cstdio 라이브러리의 파일 입출력보다 시간이 매우 많이 걸린다. 그래서 fstr.. 2022. 9. 26.
# 순열을 이진트리로 # 문제 # 입력 및 출력 # 풀이 분할 정복으로 풀면 된다. pair p[1000] 은 순열의 수와 depth를 쌍으로 저장할 배열 visit[1000]은 해당 순열을 트리에 넣었는지 확인하는 배열 find_max_idx(int s, int e) 함수는 p배열의 index s ~ e 범위에서 가장 큰 값이 있는 인덱스를 리턴 rec(int s, int e, depth) 함수는 재귀적으로 돌면서 트리의 depth를 구하는 함수로 이미 트리에 있는 숫자가 들어오면 리턴 #include using namespace std; ifstream fin("permutation.inp"); ofstream fout("permutation.out"); pair p[1000]; int visit[1000]; int T,.. 2022. 9. 23.
# 격자 색칠 # 문제 # 입력 및 출력 # 풀이 일단 해당 조건을 만족하기 위해선 가로든 세로든 같은 색으로 2줄 이상 칠해져야 한다. 그래서 2줄 이상 칠해져야 한다는 조건을 만족하기 위해 일단 2줄씩은 무조건 색칠하도록 했다. 그래서 사용한 배열이 cnt 배열이다. 같은 줄을 몇 줄이나 칠할 수 있는 지 세는 배열이다. 같은 줄을 2줄 이상 칠할 수 있는 경우엔 2줄씩 먼저 색칠하고 그 다음에도 색칠을 다 못한 경우가 있을 땐 2줄보다 더 많이 칠할 수 있는 색으로 전부 색칠하면 된다. 색을 칠할 때 2줄 이상이 되면 홀수가 되든 짝수가 되든 상관이 없기 때문이다. 말이 좀 헷갈리는데 6줄을 칠해야 하는 경우라면 1. 2-2-2 2. 2-4 3. 3-3 이런 방법으로 색칠할 수 있다. 처음 코딩할 땐 3번의 경우.. 2022. 9. 18.
# 달팽이 # 문제 # 입력 및 출력 # 풀이 처음에 N, N-1, N-1, N-2, N-2, ... , 2, 2, 1, 1 이 값을 빼주는 작업이 시간 초과가 걸릴 것이라고 생각했다. 왜냐하면 N이 10^7으로 매우 큰 상태기 때문이다. 근데 막상 보면 N^2번 반복되는 작업이 아니고 N번 반복되는 작업이기 때문에 시간초과는 걸리지 않는다. 엄청 복잡하게 풀어서 알고리즘을 천천히 글로 정리해봤다. 글로 쓰고 나니까 머릿속에 정리가 되는 느낌이다. #include using namespace std; long long N; long long dx[4] = { 0,1,0,-1 }; long long dy[4] = { 1,0,-1,0 }; ifstream fin("snail.inp"); ofstream fout("sn.. 2022. 9. 16.
# Interesting Gain # 문제 # 입력 및 출력 # 풀이 처음엔 r, l 의 값을 구해야 할 줄 알았는데 그냥 max1, max2, min1, min2 값만 구하면 되는 문제였다. 그래서 그냥 정렬해서 풀었다. #include #include using namespace std; ifstream fin("gain.inp"); ofstream fout("gain.out"); int main() { int t, n, gain; int arr[100001]; fin >> t; while (t--) { fin >> n; for (int i = 0; i > arr[i]; } sort(arr, arr + n); gain = arr[n - 1] + arr[n - 2] - arr[0] - arr[1]; fout 2022. 9. 11.
# 계단 오르기 # 문제 # 입력 및 출력 # 풀이 아직도 맞게 푼 건지 잘 모르겠다.. 일단 대충 규칙은 생각이 났는데 예외 부분이 너무 많아서 정리만 다섯 번 한 것 같다. 1. 맨 마지막엔 1층부터 F층까지 올라야 함 → N-=(F-1) 2. 엘리베이터 타는 횟수를 최소로 만들기 위해 한 번 오를 때 N을 최대로 줄일 수 있는 '1층부터 M층까지 오르기' 반복 cnt = N/(M-1) remain = N%(M-1) 3. 처음 시작 점 즉 F가 1이 아니고 remain이 0이면 cnt++ 4. remain 값이 0이 아니면 일단 cnt++, remain 값이 0이 아니고 F+remain > M 이면 cnt++ 3번 조건이 필요한 이유는 F가 1이 아니면 2번을 반복하기 위해 1층으로 가야하기 때문이다. 여기서 rem.. 2022. 9. 9.

티스토리툴바