[BOJ][C++] 2629번: 양팔저울

안녕하세요.오늘은 백준 2629번: 양팔저울(링크)  문제를 풀어보려고 합니다. 문제양팔 저울과 몇 개의 추가 주어졌을 때, 이를 이용하여 입력으로 주어진 구슬의 무게를 확인할 수 있는지를 결정하려고 한다.무게가 각각 1g과 4g인 두 개의 추가 있을 경우, 주어진 구슬과 1g 추 하나를 양팔 저울의 양쪽에 각각 올려놓아 수평을 이루면 구슬의 무게는 1g이다. 또 다른 구슬이 4g인지를 확인하려면 1g 추 대신 4g 추를 올려놓으면 된다.구슬이 3g인 경우 아래 과 같이 구슬과 추를 올려놓으면 양팔 저울이 수평을 이루게 된다. 따라서 각각 1g과 4g인 추가 하나씩 있을 경우 주어진 구슬이 3g인지도 확인해 볼 수 있다. 와 같은 방법을 사용하면 구슬이 5g인지도 확인할 수 있다. 구슬이 2g이면 주어진..

• format_list_bulleted PS/백준 문제
• · 2024. 11. 3.
• textsms

[BOJ][C++] 3051번 오아시스 재결합

안녕하세요.오늘은 백준 3015번: 오아시스 재결합(링크)  문제를 풀어보려고 합니다. 문제오아시스의 재결합 공연에 N명이 한 줄로 서서 기다리고 있다.이 역사적인 순간을 맞이하기 위해 줄에서 기다리고 있던 백준이는 갑자기 자기가 볼 수 있는 사람의 수가 궁금해졌다.두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다.줄에 서 있는 사람의 키가 주어졌을 때, 서로 볼 수 있는 쌍의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000)둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 2^31 나노미터 보다 작다.사람들이 서 있는 순서대로 입력이..

• format_list_bulleted PS/백준 문제
• · 2024. 10. 28.
• textsms

[BOJ][C++] 1562번 계단 수

안녕하세요.오늘은 백준 1562번: 계단 수(링크)  문제를 풀어보려고 합니다. 문제45656이란 수를 보자.이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.N이 주어질 때, 길이가 N이면서 0부터 9까지 숫자가 모두 등장하는 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. 0으로 시작하는 수는 계단수가 아니다. 입력첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 예제 입력10 예제 출력1 제한시간 제한: 2초메모리 제한: 128MB 풀이먼저 쉬운 계단 수를 풀고 오면 이해가 더 쉽다. 쉬운 계단 수에서 정의한 DP에 따르면 아래와 같은 점화식이 만들어진..

• format_list_bulleted PS/백준 문제
• · 2024. 10. 26.
• textsms

[BOJ][C++] 11401번 이항 계수 3

안녕하세요. 오늘은 백준 11401번: 이항 계수 3(링크) 문제를 풀어보려고 합니다. 문제자연수 N과 정수 K 가 주어졌을 때 이항 계수 (N, K)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 4,000,000, 0 ≤ K ≤ N) 출력(N, K)를 1,000,000,007로 나눈 나머지를 출력한다. 예제 입력5 2 예제 출력10 제한 시간 제한: 1초 메모리 제한: 256MB 풀이페르마의 소정리와 모듈러 곱셈 역원을 사용하면 쉽게 풀리는 문제였다. 우리가 구하려는 것은 (N, K) % m이다. 그리고 이항 계수의 정의에 따라 이는 아래와 같이 쓸 수 있다. 그런데 분수에서는 모듈러 연산이 그대로 적용이 안되는 문제가 발..

• format_list_bulleted PS/백준 문제
• · 2024. 10. 26.
• textsms

[BOJ][C++] 2342번 Dance Dance Revolution

안녕하세요.오늘은 백준 2342번: Dance Dance Revolution(링크)  문제를 풀어보려고 합니다. 문제승환이는 요즘 "Dance Dance Revolution"이라는 게임에 빠져 살고 있다. 하지만 그의 춤 솜씨를 보면 알 수 있듯이, 그는 DDR을 잘 하지 못한다. 그럼에도 불구하고 그는 살을 뺄 수 있다는 일념으로 DDR을 즐긴다.DDR은 아래의 그림과 같은 모양의 발판이 있고, 주어진 스텝에 맞춰 나가는 게임이다. 발판은 하나의 중점을 기준으로 위, 아래, 왼쪽, 오른쪽으로 연결되어 있다. 편의상 중점을 0, 위를 1, 왼쪽을 2, 아래를 3, 오른쪽을 4라고 정하자.처음에 게이머는 두 발을 중앙에 모으고 있다.(그림에서 0의 위치) 그리고 게임이 시작하면, 지시에 따라 왼쪽 또는 오..

• format_list_bulleted PS/백준 문제
• · 2024. 10. 16.
• textsms

[BOJ][C++] 11444번 피보나치 수 6

안녕하세요.오늘은 백준 11444번: 피보나치 수 6(링크)  문제를 풀어보려고 합니다. 문제피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. 출력첫째 줄에 n번째 피보나치 ..

• format_list_bulleted PS/백준 문제
• · 2024. 10. 14.
• textsms