건물 벽이 가로 C칸, 세로 R줄의 네모난 타일로 덮여 있다.
광고판은 타일을 한 장 이상 덮는 직사각형이고, 높이 h줄과 너비 w칸은 1 이상의 정수이다.
광고판은 타일 줄과 칸에 딱 맞춰 붙이고, 벽 밖으로 나가면 안 되며, 돌려 붙이지 않는다.
광고주는 넓이 h × w가 A 이상 B 이하인 광고판만 산다.
크기(h, w)와 붙이는 자리가 하나라도 다르면 다른 경우로 센다.
한 줄에 R, C, A, B가 빈칸으로 띄워 주어진다.
높이 h를 1부터 R까지 차례로 보며, 높이가 h인 광고판을 붙이는 경우의 수가 0보다 크면 한 줄에 h와 그 경우의 수를 빈칸 하나로 띄워 출력하라.
경우의 수가 0인 높이는 줄을 쓰지 않는다.
마지막 줄에는 "total"과 모든 높이의 경우의 수를 더한 값을 빈칸 하나로 띄워 출력하라.
수는 쉼표 없이 숫자만 쓴다.
입력
1 ≤ R ≤ 500, 1 ≤ C ≤ 500, 1 ≤ A ≤ B ≤ 250,000 (모두 정수)
출력
경우의 수가 있는 높이마다 "h 경우의 수" 한 줄, 마지막 줄 "total 합"
예시 1 · stdin
2 3 2 3
stdout
1 6
2 3
total 9
예시 2 · stdin
3 3 10 20
stdout
total 0
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
높이 h는 1부터 R까지, 너비 w는 1부터 C까지 두 겹으로 돌고, 넓이가 맞으면 붙일 자리 (R - h + 1) × (C - w + 1)가지를 더해요. 줄 수가 R인 벽에 높이 h를 붙이면 맨 위 줄이 1번부터 R - h + 1번까지라서 R - h가 아니에요. 첫째 함정은 반복의 끝이에요. Python range(1, R + 1)은 끝 값을 넣지 않아서 range(1, R)이라 쓰면 h = R을 빠뜨려요. JS·TS·Java·C#·C·C++는 for (int h = 1; h <= R; h++), 크레이콘은 반복 (h = 1; h <= R; h++)처럼 <=로 끝을 넣어요. C#의 Enumerable.Range(1, R)은 둘째 값이 끝이 아니라 개수예요. 둘째로, 안쪽 반복은 너비라 C까지 돌아요. 가로·세로가 다른 벽(500 × 1)에서 R과 C를 바꿔 쓰면 틀려요. 셋째로, "A 이상 B 이하"는 두 끝이 모두 들어가니 A <= area && area <= B예요(Python은 A <= area <= B로 이어 쓸 수 있지만 다른 언어에서는 오류가 나거나(크레이콘, Java·C#) 뜻이 달라져요(JS·TS·C·C++는 앞의 비교 결과를 B와 견줘요)). 넷째 함정은 크기예요. 높이 하나의 경우의 수는 int 안에 들지만, 500 × 500 벽에서 합은 약 1.6×10^10이라 C·C++ long long, Java·C# long에 더해요. JS·TS·크레이콘의 수는 2^53까지 정확하고 Python int는 넘치지 않아요.
Pythonmain.py · 11 줄
R, C, A, B = map(int, input().split())total = 0for h in range(1, R + 1): # range의 끝은 들어가지 않는다: R까지 돌려면 R + 1 count = 0 for w in range(1, C + 1): if A <= h * w <= B: count += (R - h + 1) * (C - w + 1) # 위쪽 줄 R-h+1가지 × 왼쪽 칸 C-w+1가지 if count > 0: print(h, count) total += countprint("total", total)
JavaScriptmain.js · 14 줄
const [R, C, A, B] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const out = [];let total = 0; // 최대 약 1.6×10^10: 2^53 안이라 Number로 정확하다for (let h = 1; h <= R; h++) { let count = 0; for (let w = 1; w <= C; w++) { const area = h * w; if (A <= area && area <= B) count += (R - h + 1) * (C - w + 1); } if (count > 0) out.push(`${h} ${count}`); total += count;}out.push(`total ${total}`);console.log(out.join("\n"));
TypeScriptmain.ts · 15 줄
import { readFileSync } from "node:fs";const [R, C, A, B]: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const out: string[] = [];let total = 0; // 최대 약 1.6×10^10: 2^53 안이라 number로 정확하다for (let h = 1; h <= R; h++) { let count = 0; for (let w = 1; w <= C; w++) { const area: number = h * w; if (A <= area && area <= B) count += (R - h + 1) * (C - w + 1); } if (count > 0) out.push(`${h} ${count}`); total += count;}out.push(`total ${total}`);console.log(out.join("\n"));
JavaMain.java · 21 줄
import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int R = sc.nextInt(), C = sc.nextInt(), A = sc.nextInt(), B = sc.nextInt(); StringBuilder out = new StringBuilder(); long total = 0; // 최대 약 1.6×10^10: int로는 넘친다 for (int h = 1; h <= R; h++) { long count = 0; for (int w = 1; w <= C; w++) { int area = h * w; if (A <= area && area <= B) count += (long) (R - h + 1) * (C - w + 1); } if (count > 0) out.append(h).append(' ').append(count).append('\n'); total += count; } out.append("total ").append(total).append('\n'); System.out.print(out); }}
C#Main.cs · 27 줄
using System;using System.Linq;using System.Text;class Program{ static void Main() { int[] v = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); int R = v[0], C = v[1], A = v[2], B = v[3]; var out_ = new StringBuilder(); long total = 0; // 최대 약 1.6×10^10: int로는 넘친다 for (int h = 1; h <= R; h++) { long count = 0; for (int w = 1; w <= C; w++) { int area = h * w; if (A <= area && area <= B) count += (long)(R - h + 1) * (C - w + 1); } if (count > 0) out_.Append(h).Append(' ').Append(count).Append('\n'); total += count; } out_.Append("total ").Append(total).Append('\n'); Console.Write(out_); }}
C++main.cpp · 17 줄
#include <iostream>int main() { int R, C, A, B; std::cin >> R >> C >> A >> B; long long total = 0; // 최대 약 1.6×10^10: int로는 넘친다 for (int h = 1; h <= R; h++) { long long count = 0; for (int w = 1; w <= C; w++) { int area = h * w; if (A <= area && area <= B) count += (long long)(R - h + 1) * (C - w + 1); } if (count > 0) std::cout << h << ' ' << count << '\n'; total += count; } std::cout << "total " << total << '\n';}
Cmain.c · 18 줄
#include <stdio.h>int main(void) { int R, C, A, B; scanf("%d %d %d %d", &R, &C, &A, &B); long long total = 0; /* 최대 약 1.6×10^10: int로는 넘친다 */ for (int h = 1; h <= R; h++) { long long count = 0; for (int w = 1; w <= C; w++) { int area = h * w; if (A <= area && area <= B) count += (long long)(R - h + 1) * (C - w + 1); } if (count > 0) printf("%d %lld\n", h, count); total += count; } printf("total %lld\n", total); return 0;}
Craykonmain.cray · 25 줄
v = 콘솔.수들읽기();R = v[0];C = v[1];A = v[2];B = v[3];total = 0; // 최대 약 1.6×10^10: 2^53 안이라 정확하다반복 (h = 1; h <= R; h++){ count = 0; 반복 (w = 1; w <= C; w++) { area = h * w; 만약 (A <= area && area <= B) { // 위쪽 줄 R-h+1가지 × 왼쪽 칸 C-w+1가지 count += (R - h + 1) * (C - w + 1); } } 만약 (count > 0) { 콘솔.쓰기(h + " " + count); } total += count;}콘솔.쓰기("total " + total);