어흥

문제 링크: https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 1. 주의할 점 - 2차 배열을 통해 기존의 값을 메모하고 있어야한다(메모아이제이션 기법) 2. 구현 - 1개의 정수를 통해 원하는 정수를 나타내는 경우는 모두 1로 처리해준다 - N개의 정수를 통해 원하는 정수(Tot)를 만드는 경우의 수는 N-1개의 정수 + 1개의 정수 = Tot와 같이 만든다고 생각한다. 단, 1개의 정수는 0~Tot - (N-1개 정수의 합)까지 가능하다 #include using namespace std; long long arr[201][201];//(앞의 번호)개를 사용하여 (뒤의..

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXCjsn0KJzcDFAX0 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 주의할 점 - 일반적인 재귀로 할 경우 TLE가 발생한다 - 순차적으로 하나씩 더하면서 진행한다 2. 구현 - T,A,B에 대한 정보를 모두 입력받아서 List에 저장한다 - X의 값이 정해지면, DP[1] 에 X값을 대입하고 DP[N]까지 구한다. 모든 과정에서 MOD로 나눴을 때 나머지를 입력한다 import java.io.BufferedReader; import java.io..

문제 링크: https://www.acmicpc.net/problem/17090 17090번: 미로 탈출하기 크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문자가 U인 경우에는 (r-1, c)로 이동해야 한다. R인 경우에는 (r, c+1)로 이동해야 한다. D인 경우에는 (r+1, c)로 이동해야 한다. L인 경우에는 (r, c-1)로 이동해야 한다. 미로에서 탈출 가능한 칸의 수를 계산해보자. 탈출 가능한 www.acmicpc.net 1. 주의할 점 - DFS를 통해 구현이 가능하지만, 메모라이즈 기법과 함께 사용하지 않으면 TLE가 발생한다 - 메..

문제 링크: https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 주의할 점 - "RGB거리"문제와 시작점과 끝점이 접해져 있다는 가정만 제외하면 똑같다 - 시작점과 끝점이 같다면 최소값으로 치면 안된다 2. 구현 - Cost[]: 집에 색을 칠했을 때 지불해야 하는 비용 - DP[N][3]: N번째 집에 R,G,B를 칠했을 때 지불해야 하는 총 비용 - 첫 번째 집에 M번을 칠했다는 가정하에 구하..

문제 링크: https://www.acmicpc.net/problem/2011 > str; dp[0] = 1; dp[1] = 1; if (str[0]-'0' == 0) cout

문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWaJ4g86WA4DFAUQ SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1. 주의할 점 - 위상정렬과 관련된 문제처럼 보이지만 DP와 관련된 문제다(메모라이즈 기법 사용) - DFS -> 시간초과 - 선수들은 1번부터 Node번호까지 있다 - 비트연산을 할 줄 모르면 고생한다(내가 그 예시다. 비트연산을 사용하지 않고도 할 수는 있지만 되게 더럽고 복잡해보인다. 그 시간에 비트연산을 공부하자) 2. 구현 - 첫 번째 접근: 위상정렬 위상정렬 알고리즘을 이용..

[팰린드롬] 문제 링크: https://www.acmicpc.net/problem/2079 2079번: 팰린드롬 문제 팰린드롬(palindrome)이란 앞에서부터 읽으나 뒤에서부터 읽으나 같은 단어를 말한다. 'aba'나 'a'와 같은 단어는 팰린드롬이며, 'abaccbcb'나 'anavolimilana'와 같은 단어는 팰린드롬이 아니다. 만일 어떤 단어가 팰린드롬이 아니라면, 그 단어는 여러 개의 팰린드롬으로 나누어질 수 있을 것이다. 단어가 주어졌을 때 이를 여러 개의 팰린드롬으로 나누되, 나누어진 팰린드롬의 개수가 최소가 되도록 나누려고 한다. 예를 들어 ab www.acmicpc.net [팰린드롬 분할]문제 링크: https://www.acmicpc.net/problem/1509 1509번: 팰린..

문제 링크: https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 1. 주의할 점 - DP문제다. 백트레킹으로 접근할 생각하지 말자 - DP문제라는건 알았지만 점화식을 세우는게 쉽지 않다. 문제를 해결하고 다른사람들의 점화식을 확인해본 결과 나와 같은 점화식은 찾지못했다(내가 너무 어렵게 해결한것 같다). 2. 구현 - 우선 나는 0,1로 이루어진 비트라고 생각하고 접근했다(문제와 달리 행:2 , 열:N이라고 가정) - DP[숫자의 길이(=N)][마지막에서 2번째 번호][마지막 번호] 의 형태로 배열을 세웠다. ex)[N][0][0] : N의 길이면서 마지지막이 00으로 끝나는 수,..