본문 바로가기

분류 전체보기

 (115)
백준 1463 1로 만들기 #include #include #include using namespace std; int memo[1000001]; int main() { int n; cin >> n; int count = 0; //cout
백준 10844 쉬운 계단 수 아니 왜 이 스킨은 글쓰기 버튼이 없는거지 내가 못찾나 아 깔끔해서 다 좋은데 글쓰기 버튼이 없어 왜ㅠㅠ 힝 어쨋든...... 쉬운 계단 수 문제이다 쉬운.... 쉽지 않았다 이전 숫자에 대해 그 다음 숫자가 적절하게 오는 경우의 수만 계산 하면 돼겠다! 라고 생각하고 햐! 쉽네! 라고 생각했는데 0 이라는 복병이.. 그래서 이전 자리에 오는 수가 무엇이냐에 따라 다르게 생각했다 이전 자리가 0이면 다음 자리에 1이 오고 이전 자리가 1이면 다음 자리에 0이나 2가 오고 이전 자리가 2이면 다음 자리에 1이나 3이 오고 .... 이전 자리가 8이면 다음 자리에 7이나 9가 오고 이전 자리가 9이면 다음 자리에 8이 온다 점화식을 써보면 DP(0, len) = DP(1, len -1)DP(1, len) =..
백준 2293 동전1 재귀로 호출했고 int[10001][101]을 메모이제이션으로 이용. 풀이방식은 DP(won,k) = DP(won - C[k] * 1) + DP(won - C[k] * 2) + ... + DP(won - C[k] * (won/C[k]) ) 라고 생각해서 고대로 나타냈다. won은 돈, C[k]는 k번째 코인의 가격이다. 근데 이대로 풀어서 맞으려면 coinWorth배열, 즉 동전의 가격을 정렬해야 하는데, 왠지 입력을 오름차순으로 친절하게 줄것 같아서 그냥 제출했다. 오답뜨면 그때 오름차순 해보지 머~ 하고 대충 생각함 ㅎ 메모이제이션으로 활용한 배열인 memo[i][j] 는 'j개의 코인으로 i돈을 만들기 위한 가짓 수'이다 처음 시도한 코드. #include using namespace std; in..

티스토리툴바