아이디어 재귀를 연습하기에 좋은 문제였다. 재귀의 base case는 길이가 1일때이다. (길이가 1일때는 팰린드롬이다.) 길이가 2 이상인 경우는, 문자열을 반으로 나눈다. 길이가 짝수인 경우, 반으로 그대로 나누고, 홀수인 경우는 가운데 문자를 기준으로 반으로 나눈다. 이때 반으로 나눈 문자열 다르다면 바로 "아카라카"의 조건에서 탈락이다. 반으로 나눈 그 문자열을 다시 재귀함수의 인자로 넣음으로서 해당 문자열 또한 "아카라카"인지 검사한다. 반으로 나눈 기준 앞 뒤의 문자열이 모두 아카라카라면 합친 문자열 또한 아카라카이다. https://www.acmicpc.net/problem/23304 23304번: 아카라카 주어진 문자열 $S$가 아카라카 팰린드롬이라면, AKARAKA를 출력한다. 만약 그렇..

n의 입력이 작기 때문에 브루트포스(완전 탐색)으로 풀어도 무리가 없다. 자신보다 키, 몸무게 둘 다 큰 경우 cnt++한다. https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net #include #include #include using namespace std; vector v; int main(void){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,x, ans = 0..

아이디어 처음엔 삼각형의 위에서부터 1층, ..., k층, ..., n층으로 생각하고 k층까지의 최적의 경로가 n층까지의 최적의 경로에 포함될 것이라 생각할 수도 있다. 그러나 예시로 주어진 테스트케이스가 그 반례이다. 따라서 최적의 경로는, 2차원배열의 각 인덱스에 해당하는 dp[i][j]에 저장되어있다. 그러므로 dp[i][j]에 도달하는 optimal한 경로와 dp[i][j+1]에 도달하는 경로가 다를 것이다. dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + arr[i][j]; 를 사용하여 해결하면 된다. 다시 말하자면, k층까지 탐색했을 때 합이 최대가 되는 것이 최적의 경로가 아니라, k층의 l열을 오는 데에 합이 최대가 되는 경로가 최적의 경로(dp의 점화식)을 구..

완전탐색으로 해결했다. https://www.acmicpc.net/problem/8892 8892번: 팰린드롬 팰린드롬은 어느 방향으로 읽어도 항상 같은 방법으로 읽을 수 있는 단어이다. 예를 들어, civic, radar, rotor, madam은 팰린드롬이다. 상근이는 단어 k개 적혀있는 공책을 발견했다. 공책의 단어는 ICPC www.acmicpc.net #include #include #include #include #include using namespace std; const int MAX = 1001; int t; vector v; int palindrome() { for (int i = 0; i < v.size() - 1; i++) { for (int j = i + 1; j < v.size..

https://www.acmicpc.net/problem/11091 11091번: 알파벳 전부 쓰기 팬그램은 26개의 알파벳, a~z를 최소 한번씩 모두 사용한 문장을 말한다. 아마 가장 유명한 문장은 이것일 것이다. "The quick brown fox jumps over the lazy dog." 꿍은 다른 문장들중에 팬그램인 것은 없는지 www.acmicpc.net 문제의 태그(분류)는 구현+문자열이다. 이런 문제가 처음 써보는 언어를 맛보기도 좋고 구현 능력에도 도움이 되겠지만 풀 때의 컨디션에 따라 즐겁기도, 지루하기도 한 것 같다. getline으로 s를 입력받고, 해당 문자가 존재함을 alphabet이라는 bool형 배열에 체크했다. 이후 alphabet이 false, 즉 해당 인덱스의 알파..

https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 1. A와 B의 길이가 다르면, 짧은 것이 먼저 온다. 2. 만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다) 3. 만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다. 위의 주어진 조건에 맞게 sort에 사용될 compare함수(이하 cmp)를 작..

아이디어 명령어 입력 전후를 구분하여 주사위에 새겨질 값을 바꿔야하기 때문에 dice[]배열과 new_dice[]배열 두개를 선언한다. 입력된 명령어가 1,2,3,4인 경우 각각 dice[] 및 지도 arr[x][y] 배열을 조건에 맞게 기록한다. 문제에 힌트가 주어졌다. 위 숫자들을 dice[] 및 new_dice[]의 index라고 생각하자. new_dice[]라는 지역 변수에 직전의 주사위 값인 dice[]의 값을 기록한다. 그리고 x또는 y의 값을 증감하여 다음에 탐색할 지도의 위치를 찾는다. 이때, 만약 바깥으로 이동시키려고 하는 경우에는 해당 명령을 무시해야 하며, 출력도 하면 안 된다. 라고 했으므로 매 명령어마다 실행하려는 x 또는 y의 증감이 지도의 범위를 벗어나는지 체크해야한다. new..

아이디어 아스키 코드 차트표를 참고하면 대문자와 소문자가 십진수로 32가 차이나는 것을 알 수 있다. 따라서 소문자 a를 기준으로(97) 대소문자를 구분해서 대문자라면 32를 더하여 char로 출력하고, 소문자라면 32을 뺀다. 코드 #include #include using namespace std; using ll = long long; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); string s; cin >> s; for (int i = 0; i < s.size(); i++) { if (s[i] < 97) { cout

아이디어 1. input 2차원 배열을 예제의 모양대로 처럼 표현하기 위해서 그대로 넣을 수 없고 for (int i = y1; i < y2; i++) { for (int j = x1; j < x2; j++) { arr[m-i-1][j] = 1; } } 를 거쳐야 한다. 2. dfs dfs를 진행하면서, 인접한 행렬은 visit되었다고 체크해주고, main함수에서 이차원 배열이 visit되었는지 세면서 섬처럼 인접한 부분을 cnt해주면 분리된 영역의 개수를 알 수 있다. 여기서 각 분리된 영역의 넓이를 알기 위해 visit되지 않은 칸에 (값은 0) dfs함수가 재귀적으로 호출될 때마다 영역의 넓이를 더해줬다. 그리고 매 영역마다 넓이를 0으로 다시 초기화한다. 코드 #include #include #i..

수의 규칙을 보고 떠오르는 점화식을 적었다. dp[MAX] 배열에 저장했다. 자료형이 long long이 되어야 함에 유의하자. #include using namespace std; using ll = long long; const int MAX = 105; int n,t; ll dp[MAX]; int main(void) { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); dp[1] = 1; dp[2] = 1; dp[3] = 1; for (int i = 4; i > t; while (t--) { int n; cin >> n; cout