#백준 #BOJ #BAEKJOON #알고리즘 #풀이 #C++2 BOJ백준 9019 DSLR 풀이(C++) 문제 링크 이번 문제는 BFS 문제이다.BFS문제는 현재 상태와 다음 상태에 대한 관계를 정의하는 것이 첫 번째라고 볼 수 있다.이번 문제에서는 현재 상태와 다음 상태는 D S L R로 이루어지는 문자열의 길이로 판가름난다.예를 들어 현재 상태가 L 이라면 다음으로 갈 수 있는 상태는 LD, LS, LL, LR 이렇게 네 가지이다.즉 현재가 500이라면 다음 상태는 1000, 499, 5000, (00)50이 되는 것이다. 좀 더 프로그래밍적으로 접근해보자.예를 들어 초기값이 1234이고 3412를 만든다고 해보자.먼저 초기값 1234와 빈 문자열을 c++에서 지원하는 자료형인 pair로 묶어 큐에 넣어준다.그 후 큐(queue)가 빌 때까지 아래와 같이 반복문을 돈다.1. 의 첫번째 데이터를 가져오고 .. 2019. 2. 8. BOJ백준 1748 수 이어 쓰기1 풀이(C++) 문제는 위와 같이 간단하다.단순히 연속된 수를 옆으로 쭉 나열하면서 N까지 이어썼을 때의 자릿수, 즉 문자열의 길이를 구하면 된다. 간단히 증가하는 자릿수의 규칙을 찾아보자 - 한 자리 수(1 ~ 9)123456789 -> 9자리- 두 자리 수(10 ~ 99)101112...979899 -> 180자리... 보다시피 (각 자리의 길이) * (각 자리 숫자의 개수) 가 해당 자리수까지 전부 더했을 때 증가되는 문자열의 길이임을 알 수 있다.만약 입력으로 받은 N이 네 자리 숫자라면 3자리 숫자까지는 전부 더해지므로 위의 공식대로 증가시키고 입력받은 숫자의 길이인4자리수 부터는 따로 계산해주면 쉽게 답을 구할 수 있을 것이다. 아래는 코드이다.12345678910111213141516171819202122#.. 2019. 2. 6. 이전 1 다음
