본문 바로가기

알고리즘/백준 BOJ119

[ BOJ/C# ] 9461 파도반 수열 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 문제 자체에 케이스도 많이 보여주었기 때문에 쉽게 풀 수 있는 문제였다. 다만, 처음 제출이 틀렸다. DP가 틀렸을 거라는 생각을 안 했기 때문에 반례를 찾으려 뒤의 숫자들을 넣어봤다. 100까지밖에 안했기 때문에, 100 가까이 넣어보니 음수로 출력되었다. (오버플로우) 이 문제를 해결하기 위해 dp배열의 자료형을 int 대신 long으로 바꿔주었더니 해결되었다. usi.. 2023. 9. 24.
[ BOJ/C# ] 11727 2×n 타일링 2 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 2×n 타일링 문제와 거의 비슷하다. n==1이면 1개, n==2는 3, n==3는 5, n==4는 11, n==5는 21 ...로 진행된다. 이를 보면 n의 방법의 수는 (n-1)+2*(n-2)라는 것을 알 수 있다. using System; namespace B11727 { class Program { static void Main() { StreamReader sr = new StreamReader(Console.Open.. 2023. 9. 23.
[ BOJ/C# ] 11726 2×n 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 이번에도 다이나믹 프로그래밍이다. DP유형의 문제들은 몇 번 풀어보니 비슷한 느낌이다. 처음에는 메서드로 풀었는데, 시간초과가 났다. 언제 C# 시간 줄이기를 정리해야겠다. using System; namespace B11726 { class Program { static void Main() { StreamReader sr = new StreamReader(Console.OpenStandardInput()); Str.. 2023. 9. 22.
[ BOJ/C# ] 1003 피보나치 함수 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 시간제한이 0.25초이기 때문에, 피보나치수열을 저장해 가며 업데이트 해가는 방법으로 풀었다. 미리 만들어둔 배열에 최댓값 이상일 경우, 최대값+1부터 n까지의 배열을 업데이트한다. using System; using System.Text; namespace B1003 { class Program { static void Main() { StreamReader sr = new StreamReader(Console.OpenStandardInput()); StreamWriter sw = new S.. 2023. 9. 21.
[ BOJ/C# ] 9095 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 이 문제도 다이나믹 프로그래밍 문제이다. 마찬가지로 초반에 어느 정도 직접 구해보며 규칙을 찾아야 한다. n==1일 경우 1로 1개의 방법, n==2일 경우 1+1, 2로 2개 n==3일 경우 1+1+1, 1+2, 2+1, 3으로 4개, n==4일 경우 문제의 예시를 참고하면 된다. 처음에는 왜인지 단일 숫자만으로는 안된다고 생각했다..그때문인지 n==7까지 구해봤다 예시가 n==4일 경우로 나온것으로 보아, 아마 출제자의 함정이 아니었을까 싶다😂 이렇게 예시를 구해보면 1, 2, 4, 7, 1.. 2023. 9. 19.
[ BOJ/C# ] 1463 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 다이나믹 프로그래밍 유형으로 초반에 노가다를 하여 규칙을 찾아내 앞의 값을 이용하여 푸는 문제이다. 중복 조건일때, 최솟값에 1을 더해주도록 찾아나갔다. using System; using System.Text; namespace B1463 { class Program { static void Main() { StreamReader sr = new StreamReader(Console.OpenStandardInput()); StreamWriter sw = new StreamWriter(Console.OpenSt.. 2023. 9. 18.

티스토리툴바