본문 바로가기
반응형

알고리즘

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.. 더보기
14502번 14502번 - 연구소 17년 상반기 삼성 기출문제. 그때는 손도 못댔었다.. 로직은 dfs 를 이용해서 벽 3개를 세운다(이때, 벽 3개 세우는거 중복을 막기 위해 인자를 추가로 넘겨준다) 벽 3개를 세운 이후에는 bfs를 이용해서 바이러스를 퍼뜨린다. 그리고 청정지역의 갯수를 세주면서, 최대값을 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106#include#i.. 더보기
3809. 화섭이의 정수 나열 3809. 화섭이의 정수 나열 나는 그냥 N이 1000개가 최대이기 때문에, 1000의 자리 수 이전에서 최소값이 무조건 발생한다고 생각했다. 즉, N=1000 이 되어 숫자가 1000개가 있을 때 숫자가 1000개가 생길 것이다. 그렇다고 할때 수가 1개인 예를 들어 0,1,2,3,4~,9 는 1000개가 나오게 된다. 수가 2개인 예를 들어 10,11,..,99 는 999개가 나오게 된다. 수가 3개인 100,101,...999 는 998개가 나오게 된다. 수가 4개인 1000,1001,...9999는 997개가 나오게 된다. 즉 수가 4개인 값들은 997개가 나와도 절대 1000~9999를 다 나타낼 수 없기 때문에 최소값이 무조건 발생하게 된다. 나는 이점을 이용해서 main 에서 for문을 4까.. 더보기
반응형

티스토리툴바