성장 일기 - Small Step

https://www.acmicpc.net/problem/1057 풀이 처음에 생각한 아이디어!처음에 참가자가 16명이면 배열을 전부 1로 초기화 한다. 그리고 1이 연속으로 2개 나오면 둘 중 하나는 1로 다음 라운드에 진출시키고 하나는 0으로 탈락시킨다. 그리고 지민이와 한수는 둘이 연속으로 나올때 까지 1로 다음 라운드에 진출시킨다. 그리고 지민이와 한수가 연속으로 나오면 반복문을 멈추고 해당 라운드수를 출력한다. 다음은 라운드 진행을 표현한 그림이다. 연속된 1이 두 개이면 둘 중 아무거나 진출시키며 지민이와 한수의 번호는 무조건 다음 라운드로 진출시킨다. 이 경우 최대 참가자 수가 10만이라 최악의 경우 10만*10만의 시간 복잡도로 2초를 만족하지 못 한다.. 그래도 이렇게 설명하는 이유는??..

https://www.acmicpc.net/problem/10757 풀이 풀이라고할 것도 없다. 이건 그냥 아래 블로그의 답을 보고 이해한 다음 고대로 베꼇다. http://programmerchoo.tistory.com/40 구성은 크게 두 부분으로 나뉜다.1. 배열 reverseEx) 987 -> 789 2. 두 문자열 배열의 합reverse된 문자열의 합. 만약 올림수가 발생하면 다음 배열에 +1을 해준다. 처음 그림은 입력받은 문자열 A와 B이다. 그리고 A+B이다. A+B의 경우 올리수가 발생하면 배열 전체를 뒤로 밀어야되어 번거롭다. 그래서 Reverse함수를 만들어서 배열의 압뒤를 바꾸어준다. 그 뒤 두 배열을 더해주면 올림수가 발생하여도 다음 인덱스에 +1만 해주면 되기 때문에 매우 간편하..

https://www.acmicpc.net/problem/5427 풀이 얼마전에 풀었던 3055번 탈출과 매우 유사한 문제라 풀이를 생략한다.문제 푸는데 헛짓을 좀 해서...시간을 많이 소비했더니 피곤하다..... 궁금하게 하나 있는데...상근이가 먼저 이동하고 불이 퍼져도 맞다고 생각되는데 틀렷다.그래서 불을 먼저 퍼트리고 상근이를 이동시켯는데 맞았다....예외 케이스가 생각이 안 난다.. 그리고!!!! 탈출과 불 문제의 차이점이 하나가 있는데탈출은 다음에 물이 찰 곳으로 이동을 못 하며불은 다음에 불이 와도 바로 이동이 가능하여 불이 올 곳으로도 이동이 가능하다는 것이다. 제출코드12345678910111213141516171819202122232425262728293031323334353637383..

https://www.acmicpc.net/problem/1074 풀이 어렵지 않은 문제 같은데..맞추는데 시간이 오래걸린 문제이다. 처음에 문제에서 말하는대로 배열 채워가면서 정답을 출력하려고 하였으나...시간도 초과날 뿐만아니라 배열이 너무커서 선언도 안 되었다. 그래서 생각을 해보니 규칙이 있었다!!!! 위 사진에서 보는 것 처럼 왼쪽 위를 x라고 하며, 오른쪽 위 - 왼쪽 위 = y라고 하겠다. 그럼왼쪽 위 : x오른쪽 위 : x + y왼쪽 아래 : x + 2*y오른쪽 아래 : x + 3*y의 규칙이 있다. y는 N에 따라 계산가능하다.N은 1일때 1, 2일때 4, 3일때 16 ....과 같이 증가한다. 문제에서 예제로 주어진 3 7 7을 예로 들어보겠다.재귀 함수에서 전달되는 인자값은 3개이다...

https://www.acmicpc.net/problem/3055 Ah....재밌는 문제였으나......나한테는 너무 어렵게 접근한 나머지.........꽤 많은 시간을 소비하고..내 정답률도 많이 떨어뜨린 문제였다. 조만간 다시 풀어봐야지!!!! 풀이최단거리를 구하는 문제이므로 당연히!!!BFS를 이용해야 될 것 같다. 그래서 BFS로 접근하여 문제를 풀었다. 내 풀이에서 일반적인 BFS 문제들과 다른 점이 두 가지가 있다.1. 물이 퍼져나가는 것에 대한 BFS와 고슴도치의 이동에 대한 BFS, 총 BFS를 2번 사용해야 된다는 것.2. 물은 퍼져나가고 고슴도치는 길을 찾기 위해 탐색하는데 물과 두더지의 BFS를 무조건 한 차례씩 돌아가면서 돌리는 것이 아니라 물과 고슴도치 모두 BFS를 수행하면서 같..

https://www.acmicpc.net/problem/9935 풀이 문자열의 중간을 특정 문자열과 같으면 없애는 문제이다. 왠지 문제가 백준 1406번 에디터문제와 비슷한 것 같아 스택을 2개 놓고 두 스택으로 문자를 옮겨가면서 비교하여 비슷한 문자열이 있으면 제거하면서 출력했는데....코드 길이도 길어지고.....제출하니 시간초과가 떳다...ㅎㅎ 그래서 스택을 하나로 쓰기로 결정!!1. 우선 arr배열과 bomb 배열로 문자열을 입력받은 후 arr[bottom]배열이 bomb[0]과 같으면 arr[bottom]부터 bomb배열과 비교를 한다. 만약 같을 경우 arr배열을 인덱스 값에 bomb문자열 길이만큼 더해주어 폭탄이 정답을 저정하는 answer배열에 저장이 안 되게한다. 2. 그리고 cc44와..

https://www.acmicpc.net/problem/1992 풀이음..설명하기가 어려운 문제같다.우선 같은 숫자들로만 이루어져 있으면 해당 숫자만 출력을 해야된다. 혹시나 다른 숫자들이 섞여 있으면왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 구간을 나누어 같은 숫자들로만 이루어져 있으면 해당 숫자를 출력, 아니면 다시 구간을 나누어 위와 같은 순서를 반복한다. 여기서 구간으로 나누어 들어갈 때는 ()로 구간을 나누어주어야된다. 위의 구간을 보면 빨간 선으로 처음으로 구간을 나누고 다음으로 파란선 다음으로 검은선 이렇게 쪼개서 구간을 나누어 들어간다. 왜 저 입력이 (0(0011)(0(0111)01)1)인지는 설명하기 어려우니 패스하고 추가적으로 확인할만한 예제와 출력을 첨부합니다. 문제를 제대로..

https://www.acmicpc.net/problem/2089 풀이 아...이 문제는 많은 고민을 하면 스스로 풀수도 있었을 텐데...좀만 고민하다 검색을 해버렸다. 검색을 하고 느낀건 스스로 풀었으면 많은 시간이 걸렸을 거라는 것이다. 그 이유는 N이 홀수인 7일 경우 -2로 나누면 몫은 -3이 아닌 -4가 된다는 것이다.그리서 -2로 나누어줄 때 N의 나머지가 -1일 경우 몫은 (N-1)/2로 계산해주어야 된다는 것이다. 재귀를 이용하여 문제를 풀었으며, N==0일 때 return하여 함수를 나올 때 마다 1이나 0을 출력하도록 하였다. 작성한 코드123456789101112131415161718192021222324252627282930#include int N; void bi(int N){ i..

https://www.acmicpc.net/problem/1107 풀이 모든 경우의 수를 다 해보는 부르트 포스문제이다. 모든 경우의 수를 다 계산하여도 제한시간을 초과하지 않는다. 1. 여기서는 100에서 + - 버튼으로 원하는 채널까지 이동하기 위해 누른 버른의 회수 k.2. 고장난 버튼때문에 원하는 채널에서 가장 가까운 수까지 버튼을 x번 누른수 + - 버튼을 누르는 y번의 합. k와 x+y의 값을 비교하여 더 작은 값을 출력하면된다.여기서 k와 x+y는 항상 양수여야 되므로 음수이면 if문을 사용하여 양수로 바꾸어준다. 위의 1번에서 말한 k=원하는 채널 - 100; x는 예로 5000이면 5를 한 번 0을 3번 눌러야되므로 4이다.y는 목표값이 4800이고 사용 가능한 버튼으로 목표값에 가장 가..

https://www.acmicpc.net/problem/1697 풀이 목표값으로 가기위한 최단거기를 찾는 문제로 BFS문제이다. 물론 다른 방법도 있겠지만..나는 주로 최단거리 문제는 BFS로 풀려고한다. 문제에서 말하는 1초가 추가될 때마다 1층씩 더 추가해가는 것으로 생각하고 풀면된다.문제에서 x-1, x+1,x*2 총 3가지의 갈래가 있다. 여기서 방문했던 곳을 또 방문하여 큐에 저장하는 것은 불필요하므로 방문배열을 하나 더 만들어 방문 체크를 하도록하자. 작성한 코드12345678910111213141516171819202122232425262728293031323334353637383940#include int N, K, L, Q[250000], visit[100001], front = -1,..