본문 바로가기
반응형

알고리즘/BOJ

1072번 1072번 - 게임 처음 문제 봤을 때는 막 완전탐색으로 문제를 풀려고 했는데, 값이 크다보니 시간초과가 많이 걸렸던 걸로 기억한다. 다시 문제를 보니 그냥 수학적인 식으로 풀 수 있을 것 같았다. 즉, k를 이긴 횟수라고 하면 ((Y+k)/(X+k))*100 은 k번 이겼을 때 승률이라고 할 수 있다. 그런데 이 값이 기존의 Z와 달라지려면, Z+1 보다 크거나 같을 때 k 값을 구하면 된다. ((Y+k)/(X+k))*100 >= Z+1 이라고 놓고 푼다면, k값의 범위를 알 수 있게 된다. 단 승률이 100이면 더 이상 오를수가 없고, 저걸 식으로 구하면 Z가 99면 분모가 0이 되므로 값을 구할 수 없다. 따라서 Z가 99보다 크거나 같을 때와, 그렇지 않은 부분으로 구해야한다. 1234567891.. 더보기
10219번 10219번 - Meats On The Grill 아무리 생각해도 어떻게 풀어야할지 감이 안잡혔다.. 엄청 어려운거 같은데 왜 정답률이 이렇게 높을까...하면서 결국은 다른 사람들꺼를 봤다.. 그냥 전체 Grill 을 뒤집으면 되는 방법이었다. 문제를 너무 어렵게만 풀려고 하는 것 같다, 이런 획기적인 방법을 떠올리는게 더 중요한데 123456789101112131415161718192021222324252627282930313233343536#include#include using namespace std;int h, w;char map[12][12];int main(){ int tc; cin >> tc; for (int t = 1; t > h >> w; for (int i = 0; i map[i][j.. 더보기
1024번 1024번 - 수열의 합 연속된 수이기 때문에 , 맨 처음 값이 k 라고 생각하면 그 다음은 k+1, k+2, .. 이런식으로 된다. 따라서 k , k+1 , k+2, ... 이런식으로 l 길이 이상을 찾아주면 된다. 예제로 예를 들면 n=18, l=2 이기 때문에 맨 처음에는 k , k+1 을 가지고 구해본다. 이게 길이가 2이므로.. 그러면 2k+1=18 이 되어야 하므로 k는 딱 나누어 떨어지지 않아서 구할 수 없다. (정수값을 구해야 하는게 문제의 조건이므로) 그래서 그 다음에는 구한 2k+1 에 그 다음 값 k+2 를 더하면 3k+3 이 되고 , 3k+3=18 이 되어야 한다. 딱 k의 값이 정수로 나오기 때문에 k, k+1, k+2 가 정답이 된다. 처음에 n-sum>=0 체크를 하지 않았다,.. 더보기
7569번 7569번 - 토마토 3차원 BFS로 풀면 된다. 단 토마토가 익었더라고 하더라도, 거리가 짧으면 다시 큐에 넣어야 한다. 그리고 다 돌리고 나서 익지 않은 토마토가 있다면 -1을 출력해야 하고, 그렇지 않다면 dist 배열에서 가장 큰 값을 출력해야 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201.. 더보기
10216번 10216번 - Count Circle Groups 결국 연결되는 그룹이 몇개인지를 알아내면 된다. 그래서 나는 유니온 파인드를 이용해서 값을 구했다. 주어진 n개의 통신기기들을 vector 에 저장하고, 2중 for문을 통해서 각각의 거리를 측정한다. 측정 거리가 서로의 반지름의 합보다 작거나 같으면, 두 지역은 연결할 수 있으므로 merge 를 이용해서 합해준다. 이때 find 함수값을 이용해 부모가 이미 같으면 굳이 다시 merge 할 필요가 없다. 나는 처음에 거리 r을 이차원 배열에서 위,아래,오른쪽,옆으로 생각해서 문제를 잘못 풀었고, 게다가 겹치지 않고 붙어있기만 해도 통신이 된 된다는 점을 제대로 못 읽어서 처음에 헤맸다. 문제를 다시 잘 읽는 습관을 들여야겠다. 12345678910111.. 더보기
2839번 2839번 - 설탕 배달 5kg 짜리 설탕봉지를 최대한 많이 사용할 수록, 전체 사용 갯수는 줄어든다. N제한이 최대 5000이기 때문에, 최소 봉지 사용 갯수가 1000개, 최대 봉지 사용 갯수는 1666개가 되므로 충분히 시간내에 풀 수 있다. 따라서 재귀함수를 5kg 을 먼저 사용하도록 돌리면서, 정답이 나오면 프로그램을 종료한다. 하지만 만약 정답이 나오지 않으면 -1을 출력한다. 1234567891011121314151617181920212223242526272829303132333435363738#include using namespace std;int N;void go(int n,int k){ int ret = 0; if (n == N) { cout 더보기
1239번 1239번 - 차트 permutation 함수를 사용해도 되지만, 그냥 재귀함수를 통해서 모든 경우의 수를 구했다. N제한이 8이기 때문에, 충분히 구할 수 있는 경우의 수였다. 그리고 주어진 순서를 가지고 50의 값을 만들 수 있는 경우를 모두 확인한다. 이때 처음에 나는 while 문을 쓰지 않고 for문을 썼는데, 이럴 경우에 값을 더하다가 n에 막혀 더 못 더하는 경우가 발생했다. 밑에 원에서 왼쪽까지 구해야 하는데 , 오른쪽 까지만 구해서 답을 냈다. 이 오류를 못 찾아서 계속 헤맸다.. 결국 while 문을 써서 문제를 해결했다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505.. 더보기
14503번 14503번 - 로봇 청소기 내가 항상 뭔가 겁먹는 시뮬레이션 문제.. 다시 풀어보는 문제임에도 불구하고, 실수가 쪼금씩 발생했다. 방향에 따라 크게 한번 나누고, 1. 왼쪽방향으로 갈 수 있는지 탐색하고 왼쪽방향으로 이동 2. 내 주변 4방향 탐색해서 갈 수 있는 곳이 하나라도 있으면 , 방향만 바꿔주기 3. 내 주변 4방향 탐색해서 갈 수 없으면, 뒤에가 벽인지 탐색 4. 벽이면 종료, 벽이 아니면 뒤로 이동 예전에는 더 간결하게 풀었던 것 같은데.. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475.. 더보기
반응형

티스토리툴바