🐸 Problem Solving

🔗 문제 링크 : https://www.acmicpc.net/problem/9471   문제1960년, IBM의 직원 Donald Wall은 피보나치 수열을 m으로 나눈 나머지가 주기를 이룬다는 것을 증명했다. 예를 들어, 피보나치 수열의 처음 10개를 11로 나눈 예는 다음과 같다.나머지를 이용해서 만든 수열은 주기가 나타날 수 있다. k(m)을 반복하는 부분 수열의 길이라고 했을 때, k(11) = 10 임을 알 수 있다. Wall은 아래와 같은 여러 가지 성질도 증명했다. m > 2인 경우에 k(m)은 짝수이다. 임의의 짝수 정수 n > 2에 대해서, k(m) = n인 m이 항상 존재한다. k(m) ≤ m2 - 1 k(2n) = 3×2(n-1) k(5n) = 4×5n k(2×5n) = 6n n >..

🔗 문제 링크 : https://www.acmicpc.net/problem/1932   문제 7 3 8 8 1 0 2 7 4 44 5 2 6 5위 그림은 크기가 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다. 삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.     입출력 예시    풀이 #include #in..

💣 무슨 짓을 해도 테스트케이스 절반이 통과가 안 된다! 정~말 무식하게 문제를 해결하려 했다. 뒤로 갈수록 피보나치 수가 어마어마하게 커져서 int형의 범위를 넘어간다는 건 디버깅을 통해 진즉에 알아챘지만..이걸 long으로 바꿔보고 long long으로 바꿔보고 unsigned long long으로도 바꿔보고...   결국 다 처참하게 실패하고 다시 int형 내에서 해결해 내야겠다는 생각을 먹으니... 결국 해결해 버렸다.   문제피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4)..

문제정수 배열 numLog가 주어집니다. 처음에 numLog[0]에서 부터 시작해 "w", "a", "s", "d"로 이루어진 문자열을 입력으로 받아 순서대로 다음과 같은 조작을 했다고 합시다."w" : 수에 1을 더한다."s" : 수에 1을 뺀다."d" : 수에 10을 더한다."a" : 수에 10을 뺀다.그리고 매번 조작을 할 때마다 결괏값을 기록한 정수 배열이 numLog입니다. 즉, numLog[i]는 numLog[0]로부터 총 i번의 조작을 가한 결과가 저장되어 있습니다. 주어진 정수 배열 numLog에 대해 조작을 위해 입력받은 문자열을 return 하는 solution 함수를 완성해 주세요.       입출력 예시     풀이 #include #include #include using name..

문제정수 n과 문자열 control이 주어집니다. control은 "w", "a", "s", "d"의 4개의 문자로 이루어져 있으며, control의 앞에서부터 순서대로 문자에 따라 n의 값을 바꿉니다."w" : n이 1 커집니다."s" : n이 1 작아집니다."d" : n이 10 커집니다."a" : n이 10 작아집니다.위 규칙에 따라 n을 바꿨을 때 가장 마지막에 나오는 n의 값을 return 하는 solution 함수를 완성해 주세요.      입출력 예시     풀이 #1입력 받은 문자에 따른 처리 방법을 메뉴얼(manual)로 작성한 풀이#include #include using namespace std;int solution(int n, string control) { int answer..

문제길이가 n이고, "수박수박수박수...."와 같은 패턴을 유지하는 문자열을 리턴하는 함수, solution을 완성하세요. 예를들어 n이 4이면 "수박수박"을 리턴하고 3이라면 "수박수"를 리턴하면 됩니다.      입출력 예시    풀이 #include using namespace std;string solution(int n) { string answer = ""; for (int i = 0; i

문제1부터 6까지 숫자가 적힌 주사위가 네 개 있습니다. 네 주사위를 굴렸을 때 나온 숫자에 따라 다음과 같은 점수를 얻습니다. 네 주사위에서 나온 숫자가 모두 p로 같다면 1111 × p점을 얻습니다.세 주사위에서 나온 숫자가 p로 같고 나머지 다른 주사위에서 나온 숫자가 q(p ≠ q)라면 (10 × p + q)2 점을 얻습니다.주사위가 두 개씩 같은 값이 나오고, 나온 숫자를 각각 p, q(p ≠ q)라고 한다면 (p + q) × |p - q|점을 얻습니다.어느 두 주사위에서 나온 숫자가 p로 같고 나머지 두 주사위에서 나온 숫자가 각각 p와 다른 q, r(q ≠ r)이라면 q × r점을 얻습니다.네 주사위에 적힌 숫자가 모두 다르다면 나온 숫자 중 가장 작은 숫자 만큼의 점수를 얻습니다. 네 주사..

문제1부터 6까지 숫자가 적힌 주사위가 세 개 있습니다. 세 주사위를 굴렸을 때 나온 숫자를 각각 a, b, c라고 했을 때 얻는 점수는 다음과 같습니다. 세 숫자가 모두 다르다면 a + b + c 점을 얻습니다.세 숫자 중 어느 두 숫자는 같고 나머지 다른 숫자는 다르다면 (a + b + c) × (a2 + b2 + c2 )점을 얻습니다.세 숫자가 모두 같다면 (a + b + c) × (a2 + b2 + c2 ) × (a3 + b3 + c3 )점을 얻습니다.세 정수 a, b, c가 매개변수로 주어질 때, 얻는 점수를 return 하는 solution 함수를 작성해 주세요.      입출력 예시     풀이 using namespace std;int solution(int a, int b, int c) ..

문제1부터 6까지 숫자가 적힌 주사위가 두 개 있습니다. 두 주사위를 굴렸을 때 나온 숫자를 각각 a, b라고 했을 때 얻는 점수는 다음과 같습니다. a와 b가 모두 홀수라면 a2 + b2 점을 얻습니다.a와 b 중 하나만 홀수라면 2 × (a + b) 점을 얻습니다.a와 b 모두 홀수가 아니라면 |a - b| 점을 얻습니다.두 정수 a와 b가 매개변수로 주어질 때, 얻는 점수를 return 하는 solution 함수를 작성해 주세요.    입출력 예시     풀이 using namespace std;int solution(int a, int b) { if (a & 1 && b & 1) return a * a + b * b; else if (a & 1 || b & 1) ..

💣 시간초과!vector내에서 원하는 원소를 찾기위해 std::find()를 신나게 사용했다가 일부 테스트케이스에서 시간초과가 뜨는 문제가 생겼다... 인자로 들어오는 vector들의 크기가 매우 큰 경우에 뜨는 것 같았다. 탐색하는데에 시간을 줄이기 위해 unordered_map형 인덱스를 생성하여 데이터를 찾을 때 인덱스를 참고하는 식으로 해결했다.     문제얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "so..