[Python] 백준 1744번 - 수 묶기 (골드 4)
혼자 힘으로 풀었는가? O알고리즘 분류 - 브루트포스 알고리즘 - 정렬 - 많은 조건 분기 https://www.acmicpc.net/problem/1744 문제길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 ..
2024. 6. 19.
[Python] 백준 10942번 - 팰린드롬? (골드 4)
혼자 힘으로 풀었는가? O알고리즘 분류 - 다이나믹 프로그래밍 (DP) https://www.acmicpc.net/problem/10942 문제명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.S = 3, ..
2024. 6. 17.
[Java/Python] 백준 2448번 - 별 찍기11 (골드 4)
혼자 힘으로 풀었는가? X알고리즘 분류 - 재귀 https://www.acmicpc.net/problem/2448 문제예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.입력첫째 줄에 N이 주어진다. N은 항상 $ 3×2^k $ 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) 출력첫째 줄부터 N번째 줄까지 별을 출력한다. 재귀는.. 어렵다... 우선 규칙을 찾아야 한다. 수는 3, 6, 12, 24, 48...로 늘어나며 모든 패턴은 위와 같이 나온다. 우리가 찾아야 할 것은 가장 맨 위 *을 찾는 것이다. 3일 때 *의 위치를 배열로 기준하면 (0, 2)6일 때 *의 위치는 (0, 5)와 (3, 2), (3, 8)12일 때 위치는 (0, 11) / (3, 8)..
2024. 6. 11.