# 1463

16개의 포스트
post-thumbnail

백준 1463번 1로 만들기 Class 3 문제 (Python, BFS, DP, Silver3)

백준 1463번 1로 만들기 문제 바로가기 문제 이해 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 문제 접근 문제를 보고 이거 그냥 단순한 BFS문제구나? 해서 바로 BFS로 풀었다. 근데 다 풀고나서 제출 후에 검색해보니 DP로 많이들 풀어서 나도 DP로도 풀어봤다. BFS BFS로 푸는 방식은 좀 직관적이다. 시작하는 수 N을 큐에 넣고 1을 감소시키기, 2로 나눌 수 있다면 나누기, 3

2023년 9월 8일
·
0개의 댓글
·
post-thumbnail

dp (dynamic programing) 동적 계획법 공부

1463 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 정답 d = [0] * n 이면 0이 첫번째, 1이 두번째... 가 되므로 n+1로 설정해 0은 제외하고 1이 첫번째 2가 두번째... 가 된다 다음에 계산할 나누기가 1을 뺀 값보다 작거나 큼에 따라 어차피 교체되기 때문에 범위는 2부터 시작 <span style="color:s

2023년 9월 6일
·
0개의 댓글
·
post-thumbnail

[백준] 1463번: 1로 만들기 - Java, 자바

문제접근 이번에는 bottom-up방식으로 문제를 풀어보자. bottom-up방식으로 문제를 풀 때는 아래서부터 어떠한 방식으로 dp배열을 채워나갈 것인가에 생각을 하게 된다. 1부터 차근차근 채워나가보자. 이 문제에서는 3가지 경우의 수를 갖고 있는데 x가 3으로 나누어 떨어지면 3으로 나눈다. x가 2로 나누어 떨어지면 2로 나눈다. 1을 뺀다. 이제부터 채워나갈 dp 배열은 값 N에 대하여 2 또는 3으로 나누어 떨어지면(N % 3 or 2 = 0;) 해당 값 중 가장 작은 값을 dp배열에 채워

2023년 8월 29일
·
0개의 댓글
·
post-thumbnail

백준 1463 Java

문제 답안제출 패턴찾는데 너무 오래 걸려서 결국 찾아본 문제. 문제 출력 부분에 연산하는 횟수의 최솟값을 출력하라고 적혀있음. -> 문제를 잘 읽자.

2023년 4월 25일
·
0개의 댓글
·
post-thumbnail

BOJ1463_1로 만들기

개요 최단거리로 1에 도달할 수 있는 경우를 구현해봅시다 문제 접근 $x$가 3으로 나누어 떨어지면, 3으로 나눈다. $x$가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다 정수$N$의 범위 : 0 3으로 나누어 "떨어지면" 3으로 나눈다 잘못 생각하면 3으로 나누어 떨어지면 무조건 3으로 나누어야 될거라 생각했지만 이것은 위 문제의 힌트다 10 -> 9인걸 보았을 때

2023년 2월 6일
·
0개의 댓글
·
post-thumbnail

[SW사관학교 정글/31일차 TIL] 백준 1463 : 1로 만들기(파이썬)

1로 만들기 1463번: 1로 만들기 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 예제 입력 1 예제 출력 1 예제 입력 2 예제 출력 2 힌트 10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다. 알고리즘 분류 [다이나믹 프로그래밍](https://www.acmicpc.net/probl

2022년 10월 19일
·
0개의 댓글
·

Dynamic Programming

Was ist Dynamic Programming? > 하나의 문제는 단 한 번만 풀도록 하는 알고리즘 일반적인 분할 정복 기법은 동일한 문제를 다시 푼다는 단점이 있음 ex) 피보나치 수열 : 특정한 숫자를 구하기 위해 그 앞에 있는 수자와 두 칸 앞에 있는 숫자의 합을 구해야 함 > D[i] = D[i-1] + D[i-2] -> 동일한 문제를 반복해서 계산하게 됨 하지만 정렬의 경우, 분할 정복 기법 사용 시 동일한 문제를 다시 푼다는 단점이 없음 DP의 기본적인 가정 > 1. 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. * 크고 어려운 문제가 있으면 그것을 먼저 잘게 나누어서 해결한 뒤, 나중에 전체의 답을 구하는 것!* 즉, DP는 메모이제이션을 사용한다! 이미 계산한 결과를 따로 저장해 둬서, 나중에 동일한 계산을 할 때 저장된 값을 반환하기만 함!! **피보나치 수열

2022년 10월 8일
·
0개의 댓글
·
post-thumbnail

[백준 C++] 1463 1로 만들기

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. https://www.acmicpc.net/problem/1463 풀이 제한시간이 0.15초이므로, 반복되는 구조를 이용해서 시간을 단축해야한다. 문제가 단조로운편이므로 DP나 그래프탐색등으로 풀수있는데 필자는 DP - top-down으로 풀었다. 보통 bottom -up이 편할것같은데 코드상으론 top-down이 간결한것같다. 이 문제는 크게 3가지경우인데, 사실은 4가지경우가 될수도있다. > x가 2로 나뉘어떨어

2022년 10월 8일
·
0개의 댓글
·
post-thumbnail

백준 - 1로 만들기(1463)

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 출력 예제 입력 1 예제 출력 1 예제 입력 2 예제 출력 2 힌트 정답 참고한 블로그 링크

2022년 9월 6일
·
0개의 댓글
·

[boj][c++] 1463 1로만들기

1463 1로 만들기 알바끝나고 스트릭 채우려고 쉬운 문제 고르다가 찾은 문제. 왜 이게 실버3일지에 대해서 고민하지 않고 문제 자체가 쉽게 느껴져서 풀었다. 그러나 아무리 식을 써도 답이 안 나와서 구글링한 결과 dp문제였다. 어쩐지 이런 문제가 직관적으로 풀리면 실버3일리가 없지 ̄へ ̄ dp...너무 옛날에 공부한거라 생각이 안 났다. 모든 경우의 수를 담을 배열 만들어서 점화식 이용해서 그 배열을 채우는거라는 딱 그정도의 지식만 있었다. 공부할 때도 점화식을 모르면 문제를 못 푸니까 어렵다고 생각했다. 구글링으로 점화식 컨닝하지 않았다면 못 풀었을 것

2022년 6월 14일
·
0개의 댓글
·
post-thumbnail

[알고리즘/백준] 1463번 : 1로 만들기(python)

리스트 대신 딕셔너리를 사용해서 값을 찾는 연산 속도를 줄일 수 있다.

2022년 3월 5일
·
0개의 댓글
·
post-thumbnail

[백준] 참쉽죠? 1463 '1로만들기' Python

very easy한 문제입니다. DP 이용해야하고요 조금 주의력이 필요한 문제입니다. 정답비율 30프로인데 아마 실수 하셔서 그럴겁니다. 저도 그랬고요 2트에 풀었네요. ![](https://images.velog.io/images/ksun4131/post/10ea18c0-5710-48f5-bd21-8e062f33f2da/%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%

2022년 1월 12일
·
0개의 댓글
·

BAEKJOON #1463 (DP) - python

1로 만들기 출처 : 백준 #1463 |시간 제한|메모리 제한| |-|-| |0.15초|128MB| 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다. 출력 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 입출력 예시 예제 입력 1 > 2 예제 출력 1 > 1 예제 입력 2 > 10 예제 출력 2 > 3 풀이

2021년 8월 2일
·
0개의 댓글
·

[BOJ]#1463 1로 만들기 Python

문제 https://www.acmicpc.net/problem/1463 >정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. > X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력 >첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력 >첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 아이디어 >다이나믹 프로그래밍 사용 ex) n=6인 경우, dp[6]이 가장 작은 경우를 구해야 한다. 우선 1을 먼저 빼는 경우를 저장해 두고, 2로 나눠지면 2로, 3으로 나눠지면 3으로 나눈 경우의 수와 비교해 작은 수를 선택한다. > 1을 빼는 경우 => dp[5]과 '6에서 1을 뺀 경우'인 1을 더한다 => dp[6

2021년 3월 31일
·
0개의 댓글
·

#1463 1로 만들기

💯 문제 → 숫자를 1로 만드는 것이 목표인 문제 ! 단, 3으로 나누거나 2로 나누거나 1을 빼는 연산만이 가능하며 연산의 횟수를 최소한으로 맞추어야되는 문제인 듯 ! 🎈 1 동적계획법 cache를 만들어 이 곳에는 각 수의 최소 연산 횟수를 저장한다. 3으로 나누어 지는 것을 기준으로 코드를 짜는데, 3으로 나누어 지지 않는 수들 중, 만약 1을 뺀 수의 연산 횟수와 2로 나눈 수의 연산 횟수를 비교하여 적용한다. 안된 이유 : 일단 채점 82%에서 계속 틀렸다고 나오는 걸 보니, 아마 큰 수에서 문제가 있는듯 .. ㅠㅠ 그 수를 알려주면 좋겠다 .. 제발 ..내 생각엔 3으로 나누어 지지 않는 부분에서 2와의 비교가 없어서 그런 것 같고 3으로 우선순위를 정해놓고 문제를 풀어서 그런듯 ! 🎈 2 동적계획법 cache를 만들어 이 곳에는 각 수의 최소 연산 횟수를 저장한다. 2로

2021년 2월 22일
·
0개의 댓글
·

2019 winter PS --version DP (day4)

백준 1463, 2579 1) 백준 1463 : 1로 만들기 (https://www.acmicpc.net/problem/1463) 처음에는 소인수분해 해서 가능한 큰 수로 나누도록 하는 문제인줄 알고 있다가, 예제 생각하면서 반례를 찾아서 벙쪄있었음. 포인트가 가장 큰 수로 나눈다고 항상 가장 적은 횟수로 1을 만들 수 있는게 아니더라. (뻘짓 오짐...) 1을 만들기 위해서 1은 0번, 2는 1번, 3은 1번의 회수로 1을 만들 수 있다. 그럼 4는? 4는 4 > 3 > 1 을가거나 4 > 2 > 1 을가거나 4 > 1.3333 > 1 을가거나 인데 마지막 1.33 은 말이 안되니까 재낀다. 그럼 저 성질들로 보아 2에서 1로가는 최소회수, 3에서 1로가는 최소회수가 다시 사용되는 것을 알 수 있다. 그럼 5는? 5 > 4 > ... > 1 (4에서 1을 가는 최단 회수는 이미 전에 구했기 때문에 저것만 보면 된다.) 6은? 6 > 5 > ... > 1 | 6 > 3 >

2019년 12월 26일
·
0개의 댓글
·